Anzeige
Erschienen in:
2012 | OriginalPaper | Buchkapitel
The Black-and-White Coloring Problem on Distance-Hereditary Graphs and Strongly Chordal Graphs
verfasst von : Ton Kloks, Sheung-Hung Poon, Feng-Ren Tsai, Yue-Li Wang
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
Given a graph
G
and integers
b
and
w
. The black-and-white coloring problem asks if there exist disjoint sets of vertices
B
and
W
with
|B|=b
and
|W|=w
such that no vertex in
B
is adjacent to any vertex in
W
. In this paper we show that the problem is polynomial when restricted to cographs, distance-hereditary graphs, interval graphs and strongly chordal graphs. We show that the problem is NP-complete on splitgraphs.