THE COMPLEXITY OF APPROXIMATING THE ORIENTED DIAMETER OF CHORDAL GRAPHS
WG
| dc.creator | Fomin, Fedor V | |
| dc.creator | Matamala Vasquez, Martin Ignacio | |
| dc.creator | Rapaport Zimermann, Ivan | |
| dc.date | 2016-12-27T21:46:40Z | |
| dc.date | 2022-06-17T21:03:27Z | |
| dc.date | 2016-12-27T21:46:40Z | |
| dc.date | 2022-06-17T21:03:27Z | |
| dc.date | 2002 | |
| dc.date.accessioned | 2023-08-22T23:47:19Z | |
| dc.date.available | 2023-08-22T23:47:19Z | |
| dc.identifier | 1010442 | |
| dc.identifier | 3-540-00331-2 | |
| dc.identifier | https://hdl.handle.net/10533/164347 | |
| dc.identifier.uri | https://repositorioslatinoamericanos.uchile.cl/handle/2250/8352553 | |
| dc.description | The oriented diameter of a (undirected) 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 give a linear time algorithm such that, for a given chordal graph G, either concludes that there is no strongly connected orientation of G, or finds a strongly connected orientation of G with diameter at most twice the diameter of G plus one; we prove that the corresponding decision problem remains NP-complete even when restricted to a small subclass of chordal graphs called split graphs; we show that, unless P = NP, there is neither a polynomial-time absolute approximation algorithm nor an ?-approximation (for every ?<3 2) algorithm computing oriented diameter of a chordal graph. The oriented diameter of a (undirected) 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 give a linear time algorithm such that, for a given chordal graph G, either concludes that there is no strongly connected orientation of G, or finds a strongly connected orientation of G with diameter at most twice the diameter of G plus one; we prove that the corresponding decision problem remains NP-complete even when restricted to a small subclass of chordal graphs called split graphs; we show that, unless P = NP, there is neither a polynomial-time absolute approximation algorithm nor an ?-approximation (for every ?<3 2) algorithm computing oriented diameter of a chordal graph. The oriented diameter of a (undirected) 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 give a linear time algorithm such that, for a given chordal graph G, either concludes that there is no strongly connected orientation of G, or finds a strongly connected orientation of G with diameter at most twice the diameter of G plus one; we prove that the corresponding decision problem remains NP-complete even when restricted to a small subclass of chordal graphs called split graphs; we show that, unless P = NP, there is neither a polynomial-time absolute approximation algorithm nor an ?-approximation (for every ?<3 2) algorithm computing oriented diameter of a chordal graph. The oriented diameter of a (undirected) 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 give a linear time algorithm such that, for a given chordal graph G, either concludes that there is no strongly connected orientation of G, or finds a strongly connected orientation of G with diameter at most twice the diameter of G plus one; we prove that the corresponding decision problem remains NP-complete even when restricted to a small subclass of chordal graphs called split graphs; we show that, unless P = NP, there is neither a polynomial-time absolute approximation algorithm nor an ?-approximation (for every ?<3 2) algorithm computing oriented diameter of a chordal graph. | |
| dc.description | FONDECYT | |
| dc.description | 0 | |
| dc.description | FONDECYT | |
| dc.language | eng | |
| dc.publisher | SPRINGER | |
| dc.relation | instname: Conicyt | |
| dc.relation | reponame: Repositorio Digital RI2.0 | |
| dc.relation | instname: Conicyt | |
| dc.relation | reponame: Repositorio Digital RI 2.0 | |
| dc.relation | LECTURE NOTES IN COMPUTER SCIENCE | |
| dc.relation | info:eu-repo/grantAgreement/Fondecyt/1010442 | |
| dc.relation | info:eu-repo/semantics/dataset/hdl.handle.net/10533/93479 | |
| dc.rights | info:eu-repo/semantics/openAccess | |
| dc.title | THE COMPLEXITY OF APPROXIMATING THE ORIENTED DIAMETER OF CHORDAL GRAPHS | |
| dc.title | WG | |
| dc.type | Capitulo de libro | |
| dc.type | info:eu-repo/semantics/bookPart |