Anzeige
Erschienen in:
2012 | OriginalPaper | Buchkapitel
Algorithms for Bandwidth Consecutive Multicolorings of Graphs
(Extended Abstract)
verfasst von : Kazuhide Nishikawa, Takao Nishizeki, Xiao Zhou
Erschienen in: Frontiers in Algorithmics and Algorithmic Aspects in Information and Management
Verlag: Springer Berlin Heidelberg
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
Let
G
be a simple graph in which each vertex
v
has a positive integer weight
b
(
v
) and each edge (
v
,
w
) has a nonnegative integer weight
b
(
v
,
w
). A bandwidth consecutive multicoloring of
G
assigns each vertex
v
a specified number
b
(
v
) of consecutive positive integers so that, for each edge (
v
,
w
), all integers assigned to vertex
v
differ from all integers assigned to vertex
w
by more than
b
(
v
,
w
). The maximum integer assigned to a vertex is called the span of the coloring. In the paper, we first investigate fundamental properties of such a coloring. We then obtain a pseudo polynomial-time exact algorithm and a fully polynomial-time approximation scheme for the problem of finding such a coloring of a given series-parallel graph with the minimum span. We finally extend the results to the case where a given graph
G
is a partial
k
-tree, that is,
G
has a bounded tree-width.