Name
Abstract | ||
|---|---|---|
The oriented diameter of a bridgeless connected undirected(bcu) graph G is the smallest diameter among all thediameters of strongly connected orientations of G. We studyalgorithmic aspects of determining the oriented diameter of achordal graph. We (a) construct a linear-time approximationalgorithm that, for a given chordal bcu graph G,finds a strongly connected orientation of G with diameter atmost one plus twice the oriented diameter of G; (b) provethat, for every k≥ 2 and k ≠ 3, to decidewhether a chordal (split for k = 2) bcu graphG admits an orientation of diameter k isNP-complete; (c) show that, unless P = NP,there is neither a polynomial-time absolute approximation algorithmnor an ±-approximation algorithm that computes the orienteddiameter of a bcu chordal graph for ± |
Year | DOI | Venue |
|---|---|---|
2004 | 10.1002/jgt.v45:4 | Journal of Graph Theory |
Keywords | Field | DocType |
diameter,orientation,algorithms,chordal graph | Discrete mathematics,Block graph,Combinatorics,Outerplanar graph,Graph power,Interval graph,Ordered graph,Distance-hereditary graph,Planar graph,Mathematics,Split graph | Journal |
Volume | Issue | ISSN |
45 | 4 | 0364-9024 |
ISBN | Citations | PageRank |
3-540-00331-2 | 11 | 0.67 |
References | Authors | |
18 | 3 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Fedor V. Fomin | 1 | 3139 | 192.21 |
| Martín Matamala | 2 | 158 | 21.63 |
| Ivan Rapaport | 3 | 199 | 21.93 |