Complexity of approximating the oriented diameter of chordal graphs

Fedor V. Fomin, Martı́n Matamala, Iván Rapaport

Journal of Graph Theory · 2004 · 26 citations · 22 references

DOIFull text

Open access

Concepts

Abstract

Abstract The oriented diameter of a bridgeless connected undirected ( bcu ) 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 (a) construct a linear‐time approximation algorithm that, for a given chordal bcu graph G , finds a strongly connected orientation of G with diameter at most one plus twice the oriented diameter of G ; (b) prove that, for every k ≥ 2 and k # 3, to decide whether a chordal (split for k = 2) bcu graph G admits an orientation of diameter k is NP ‐complete; (c) show that, unless P = NP , there is neither a polynomial‐time absolute approximation algorithm nor an α‐approximation algorithm that computes the oriented diameter of a bcu chordal graph for α < ${3\over2}$ . © 2004 Wiley Periodicals, Inc. J Graph Theory 45: 255–269, 2004

References

22