Abstract
Let G be a plane graph where each edge is a line segment. We consider the problem of computing the maximum detour of G, defined as the maximum over all pairs of distinct points p and q of G of the ratio between the distance between p and q in G and the distance |pq|. The fastest known algorithm for this problem has Theta(n^2) running time where n is the number of vertices. We show how to obtain O(n^{3/2}*(log n)^3) expected running time. We also show that if G has bounded treewidth, its maximum detour can be computed in O(n(log n)^3) expected time.
| Original language | English |
|---|---|
| Title of host publication | Algorithms and Computation : 19th International Symposium, ISAAC 2008, Gold Coast, Australia, December 15-17, 2008, Proceedings |
| Editors | Seok-Hee Hong, Hiroshi Nagamochi, Takuro Fukunaga |
| Number of pages | 12 |
| Publisher | Springer |
| Publication date | 2008 |
| Pages | 740-751 |
| ISBN (Electronic) | 978-3-540-92181-3 |
| DOIs | |
| Publication status | Published - 2008 |
| Event | International Symposium on Algorithms and Computation - Gold Coast, Australia Duration: 15 Dec 2008 → 17 Dec 2008 Conference number: 19 |
Conference
| Conference | International Symposium on Algorithms and Computation |
|---|---|
| Number | 19 |
| Country/Territory | Australia |
| City | Gold Coast |
| Period | 15/12/2008 → 17/12/2008 |
| Series | Lecture notes in computer science |
|---|---|
| Number | 5369 |
| ISSN | 0302-9743 |