Anzeige
Erschienen in:
2013 | OriginalPaper | Buchkapitel
Hardness and Algorithms for Variants of Line Graphs of Directed Graphs
verfasst von : Mourad Baïou, Laurent Beaudou, Zhentao Li, Vincent Limouzy
Erschienen in: Algorithms and Computation
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 directed graph
D
= (
V
,
A
) we define its intersection graph
I
(
D
) = (
A
,
E
) to be the graph having
A
as a node-set and two nodes of
I
(
D
) are adjacent if their corresponding arcs share a common node that is the tail of at least one of these arcs. We call them facility location graphs since they arise from the classical uncapacitated facility location problem. In this paper we show that facility location graphs are hard to recognize but they are easy to recognize when the underlying graph is triangle-free. We also determine the complexity of the vertex coloring, the stable set and the facility location problem for triangle-free facility location graphs.