Multicolorings of Series-Parallel Graphs |
| |
Authors: | Xiao Zhou and Takao Nishizeki |
| |
Affiliation: | (1) Graduate School of Information Sciences, Tohoku University, Aoba-yama 05, Sendai 980-8579, Japan |
| |
Abstract: | Let G be a graph,
and let each vertex v of G have a positive integer weight
(v).
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.
This paper presents an algorithm
to find
a multicoloring of a given series-parallel graph G
with the minimum number of colors
in
time O(n
W),
where n is the number of vertices
and W is the maximum weight of vertices in G. |
| |
Keywords: | Coloring Multicoloring Dynamic programming algorithm Series-parallel graph |
本文献已被 SpringerLink 等数据库收录! |