| 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 α <  . © 2004 Wiley Periodicals, Inc. J Graph Theory 45: 255–269, 2004 |
