Capitulo de libro
THE COMPLEXITY OF APPROXIMATING THE ORIENTED DIAMETER OF CHORDAL GRAPHS
WG
Registro en:
1010442
3-540-00331-2
Autor
Fomin, Fedor V
Matamala Vasquez, Martin Ignacio
Rapaport Zimermann, Ivan
Institución
Resumen
The oriented diameter of a (undirected) graph G is the smallest diameter among all the diameters of strongly connected orientations of G. We study algorithmic aspects of determining the oriented diameter of a chordal graph. We give a linear time algorithm such that, for a given chordal graph G, either concludes that there is no strongly connected orientation of G, or finds a strongly connected orientation of G with diameter at most twice the diameter of G plus one; we prove that the corresponding decision problem remains NP-complete even when restricted to a small subclass of chordal graphs called split graphs; we show that, unless P = NP, there is neither a polynomial-time absolute approximation algorithm nor an ?-approximation (for every ?<3 2) algorithm computing oriented diameter of a chordal graph.
The oriented diameter of a (undirected) graph G is the smallest diameter among all the diameters of strongly connected orientations of G. We study algorithmic aspects of determining the oriented diameter of a chordal graph. We give a linear time algorithm such that, for a given chordal graph G, either concludes that there is no strongly connected orientation of G, or finds a strongly connected orientation of G with diameter at most twice the diameter of G plus one; we prove that the corresponding decision problem remains NP-complete even when restricted to a small subclass of chordal graphs called split graphs; we show that, unless P = NP, there is neither a polynomial-time absolute approximation algorithm nor an ?-approximation (for every ?<3 2) algorithm computing oriented diameter of a chordal graph.
The oriented diameter of a (undirected) graph G is the smallest diameter among all the diameters of strongly connected orientations of G. We study algorithmic aspects of determining the oriented diameter of a chordal graph. We give a linear time algorithm such that, for a given chordal graph G, either concludes that there is no strongly connected orientation of G, or finds a strongly connected orientation of G with diameter at most twice the diameter of G plus one; we prove that the corresponding decision problem remains NP-complete even when restricted to a small subclass of chordal graphs called split graphs; we show that, unless P = NP, there is neither a polynomial-time absolute approximation algorithm nor an ?-approximation (for every ?<3 2) algorithm computing oriented diameter of a chordal graph.
The oriented diameter of a (undirected) graph G is the smallest diameter among all the diameters of strongly connected orientations of G. We study algorithmic aspects of determining the oriented diameter of a chordal graph. We give a linear time algorithm such that, for a given chordal graph G, either concludes that there is no strongly connected orientation of G, or finds a strongly connected orientation of G with diameter at most twice the diameter of G plus one; we prove that the corresponding decision problem remains NP-complete even when restricted to a small subclass of chordal graphs called split graphs; we show that, unless P = NP, there is neither a polynomial-time absolute approximation algorithm nor an ?-approximation (for every ?<3 2) algorithm computing oriented diameter of a chordal graph. FONDECYT 0 FONDECYT