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 approximate algorithm nor an ?-approximation algorithm that computes the oriented diameter of a bcu chordal graph for ? < 2/3. © 2004 Wiley Periodicals, Inc.