Journal of Graph Theory · 2004 · 26 citations · 22 references
ComputingComputer ScienceMathematicsAlgorithmsCombinatoricsTheory Of ComputationApproximation AlgorithmsComputational ComplexityGeometric ApproximationGeometric GraphsGraph AlgorithmsGraph TheoryApproximate DiameterChordal Graph DiameterComputational Complexity Of Graph AlgorithmsDiameter Computation AlgorithmsGraph DiameterGraph Theory AnalysisNp-complete ProblemsNp-completeness
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
22
Depth-First Search and Linear Graph Algorithms
Robert E. Tarjan · SIAM Journal on Computing · 1972 · 6K citations
Incidence matrices and interval graphs
D. R. Fulkerson, Oliver Gross · Pacific Journal of Mathematics · 1965 · 1.3K citations · Full text