The original paper is in English. Non-English content has been machine-translated and may contain typographical errors or mistranslations. ex. Some numerals are expressed as "XNUMX".
Copyrights notice
The original paper is in English. Non-English content has been machine-translated and may contain typographical errors or mistranslations. Copyrights notice
하자 l 양의 정수이고, G 간선에 음이 아닌 정수 가중치가 있는 그래프여야 합니다. 그런 다음 l-채색 of G는 정점에 색상을 할당하는 것입니다. G 임의의 두 정점이 같은 방식으로 u and v 사이의 거리가 멀면 다른 색상을 얻습니다. u and v in G 기껏해야 l. 이 논문에서는 다음을 찾는 알고리즘을 제공합니다. l-주어진 그래프의 색상 지정 G 최소한의 색상으로. 다음과 같은 경우 알고리즘에 다항식 시간이 걸립니다. G 부분적이다 k-나무와 둘 다 l and k 제한된 정수입니다.
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.
부
Xiao ZHOU, Yasuaki KANARI, Takao NISHIZEKI, "Generalized Vertex-Colorings of Partial k-Trees" in IEICE TRANSACTIONS on Fundamentals,
vol. E83-A, no. 4, pp. 671-678, April 2000, doi: .
Abstract: Let l be a positive integer, and let G be a graph with nonnegative integer weights on edges. Then a generalized vertex-coloring, called an l-coloring of G, is an assignment of colors to the vertices of G in such a way that any two vertices u and v get different colors if the distance between u and v in G is at most l. In this paper we give an algorithm to find an l-coloring of a given graph G with the minimum number of colors. The algorithm takes polynomial time if G is a partial k-tree and both l and k are bounded integers.
URL: https://global.ieice.org/en_transactions/fundamentals/10.1587/e83-a_4_671/_p
부
@ARTICLE{e83-a_4_671,
author={Xiao ZHOU, Yasuaki KANARI, Takao NISHIZEKI, },
journal={IEICE TRANSACTIONS on Fundamentals},
title={Generalized Vertex-Colorings of Partial k-Trees},
year={2000},
volume={E83-A},
number={4},
pages={671-678},
abstract={Let l be a positive integer, and let G be a graph with nonnegative integer weights on edges. Then a generalized vertex-coloring, called an l-coloring of G, is an assignment of colors to the vertices of G in such a way that any two vertices u and v get different colors if the distance between u and v in G is at most l. In this paper we give an algorithm to find an l-coloring of a given graph G with the minimum number of colors. The algorithm takes polynomial time if G is a partial k-tree and both l and k are bounded integers.},
keywords={},
doi={},
ISSN={},
month={April},}
부
TY - JOUR
TI - Generalized Vertex-Colorings of Partial k-Trees
T2 - IEICE TRANSACTIONS on Fundamentals
SP - 671
EP - 678
AU - Xiao ZHOU
AU - Yasuaki KANARI
AU - Takao NISHIZEKI
PY - 2000
DO -
JO - IEICE TRANSACTIONS on Fundamentals
SN -
VL - E83-A
IS - 4
JA - IEICE TRANSACTIONS on Fundamentals
Y1 - April 2000
AB - Let l be a positive integer, and let G be a graph with nonnegative integer weights on edges. Then a generalized vertex-coloring, called an l-coloring of G, is an assignment of colors to the vertices of G in such a way that any two vertices u and v get different colors if the distance between u and v in G is at most l. In this paper we give an algorithm to find an l-coloring of a given graph G with the minimum number of colors. The algorithm takes polynomial time if G is a partial k-tree and both l and k are bounded integers.
ER -