Generalized Vertex-Colorings of Partial k-Tress(Special Section on Discrete Mathematics and Its Applications)

スポンサーリンク

概要

• 論文の詳細を見る

• 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.

• 社団法人電子情報通信学会の論文
• 2000-04-25

著者

• Zhou Xiao

  The Authors Are With Graduate School Of Information Sciences Tohoku University

• Nishizeki Takao

  The Author Is With The Graduate School Of Information Science Tohoku University

• Nishizeki Takao

  The Authors Are With Graduate School Of Information Sciences Tohoku University

• Nishizeki Takao

  The Author Is With Graduate School Of Information Sciences Tohoku University

• KANARI Yasuaki

  The author is with Matsushita Communication Sendai R&D Labs. Co., Ltd.

• Kanari Yasuaki

  The Author Is With Matsushita Communication Sendai R&d Labs. Co. Ltd.

関連論文

• On the Average Length of Secret Key Exchange Eulerian Circuits(Special Section on Discrete Mathematics and Its Applications)
• Planar Reconfiguration of Monotone Trees(Special Section on Discrete Mathematics and Its Applications)
• Generalized Vertex-Colorings of Partial k-Tress(Special Section on Discrete Mathematics and Its Applications)

スポンサーリンク