IEICE TRANSACTIONS on Information
Algorithms for Multicolorings of Partial k-Trees
Summary :
Let each vertex v of a graph G have a positive integer weight ω(v). Then a multicoloring of G is to assign each vertex v a set of ω(v) colors so that any pair of adjacent vertices receive disjoint sets of colors. A partial k-tree is a graph with tree-width bounded by a fixed constant k. This paper presents an algorithm which finds a multicoloring of any given partial k-tree G with the minimum number of colors. The computation time of the algorithm is bounded by a polynomial in the number of vertices and the maximum weight of vertices in G.
- Publication
- IEICE TRANSACTIONS on Information Vol.E86-D No.2 pp.191-200
- Publication Date
- 2003/02/01
- Publicized
- Online ISSN
- DOI
- Type of Manuscript
- Special Section PAPER (Special Issue on Selected Papers from LA Symposium)
- Category
- Graph Algorithms
Authors
Keyword
Latest Issue
Copyrights notice of machine-translated contents
The copyright of the original papers published on this site belongs to IEICE. Unauthorized use of the original or translated papers is prohibited. See IEICE Provisions on Copyright for details.
Cite this
Copy
Takehiro ITO, Takao NISHIZEKI, Xiao ZHOU, "Algorithms for Multicolorings of Partial k-Trees" in IEICE TRANSACTIONS on Information,
vol. E86-D, no. 2, pp. 191-200, February 2003, doi: .
Abstract: Let each vertex v of a graph G have a positive integer weight ω(v). Then a multicoloring of G is to assign each vertex v a set of ω(v) colors so that any pair of adjacent vertices receive disjoint sets of colors. A partial k-tree is a graph with tree-width bounded by a fixed constant k. This paper presents an algorithm which finds a multicoloring of any given partial k-tree G with the minimum number of colors. The computation time of the algorithm is bounded by a polynomial in the number of vertices and the maximum weight of vertices in G.
URL: https://global.ieice.org/en_transactions/information/10.1587/e86-d_2_191/_p
Copy
@ARTICLE{e86-d_2_191,
author={Takehiro ITO, Takao NISHIZEKI, Xiao ZHOU, },
journal={IEICE TRANSACTIONS on Information},
title={Algorithms for Multicolorings of Partial k-Trees},
year={2003},
volume={E86-D},
number={2},
pages={191-200},
abstract={Let each vertex v of a graph G have a positive integer weight ω(v). Then a multicoloring of G is to assign each vertex v a set of ω(v) colors so that any pair of adjacent vertices receive disjoint sets of colors. A partial k-tree is a graph with tree-width bounded by a fixed constant k. This paper presents an algorithm which finds a multicoloring of any given partial k-tree G with the minimum number of colors. The computation time of the algorithm is bounded by a polynomial in the number of vertices and the maximum weight of vertices in G.},
keywords={},
doi={},
ISSN={},
month={February},}
Copy
TY - JOUR
TI - Algorithms for Multicolorings of Partial k-Trees
T2 - IEICE TRANSACTIONS on Information
SP - 191
EP - 200
AU - Takehiro ITO
AU - Takao NISHIZEKI
AU - Xiao ZHOU
PY - 2003
DO -
JO - IEICE TRANSACTIONS on Information
SN -
VL - E86-D
IS - 2
JA - IEICE TRANSACTIONS on Information
Y1 - February 2003
AB - Let each vertex v of a graph G have a positive integer weight ω(v). Then a multicoloring of G is to assign each vertex v a set of ω(v) colors so that any pair of adjacent vertices receive disjoint sets of colors. A partial k-tree is a graph with tree-width bounded by a fixed constant k. This paper presents an algorithm which finds a multicoloring of any given partial k-tree G with the minimum number of colors. The computation time of the algorithm is bounded by a polynomial in the number of vertices and the maximum weight of vertices in G.
ER -
English
