Computing the Maximum Detour of a Plane Graph in Subquadratic Time

Christian Wulff-Nilsen

doi:10.1007/978-3-540-92182-0_65

Computing the Maximum Detour of a Plane Graph in Subquadratic Time

Christian Wulff-Nilsen

Datalogisk Institut

3 Citationer (Scopus)

Abstract

Lad G være en plan graf, hvor hver kant er et linjestykke. Vi betragter problemet med at finde den maksimale omvej (detour) i G, defineret som maksimum over all par af forskellige punkter p og q (knuder såvel som indre punkter af kanter) af forholdet mellem afstanden mellem p og q i G og afstanden |pq|. Den hurtigste algoritme for dette problem har Theta(n^2) køretid, hvor n er antallet af knuder. Vi viser, hvordan man kan opnå O(n^{3/2}*(log n)^3) forventet køretid. Vi viser også, at hvis G har begrænset treewidth, så kan den maksimale omvej findes i O(n*(log n)^3) forventet tid.

Originalsprog	Engelsk
Titel	Algorithms and Computation : 19th International Symposium, ISAAC 2008, Gold Coast, Australia, December 15-17, 2008, Proceedings
Redaktører	Seok-Hee Hong, Hiroshi Nagamochi, Takuro Fukunaga
Antal sider	12
Forlag	Springer
Publikationsdato	2008
Sider	740-751
ISBN (Elektronisk)	978-3-540-92181-3
DOI	https://doi.org/10.1007/978-3-540-92182-0_65
Status	Udgivet - 2008
Begivenhed	International Symposium on Algorithms and Computation - Gold Coast, Australien Varighed: 15 dec. 2008 → 17 dec. 2008 Konferencens nummer: 19

Konference

Konference	International Symposium on Algorithms and Computation
Nummer	19
Land/Område	Australien
By	Gold Coast
Periode	15/12/2008 → 17/12/2008

Navn	Lecture notes in computer science
Nummer	5369
ISSN	0302-9743

Adgang til dokumentet

10.1007/978-3-540-92182-0_65

Citationsformater

Computing the Maximum Detour of a Plane Graph in Subquadratic Time. / Wulff-Nilsen, Christian.
Algorithms and Computation: 19th International Symposium, ISAAC 2008, Gold Coast, Australia, December 15-17, 2008, Proceedings. red. / Seok-Hee Hong; Hiroshi Nagamochi; Takuro Fukunaga. Springer, 2008. s. 740-751 (Lecture notes in computer science; Nr. 5369).

Publikation: Bidrag til bog/antologi/rapport › Konferencebidrag i proceedings › Forskning › peer review

Wulff-Nilsen, C 2008, Computing the Maximum Detour of a Plane Graph in Subquadratic Time. i S-H Hong, H Nagamochi & T Fukunaga (red), Algorithms and Computation: 19th International Symposium, ISAAC 2008, Gold Coast, Australia, December 15-17, 2008, Proceedings. Springer, Lecture notes in computer science, nr. 5369, s. 740-751, International Symposium on Algorithms and Computation, Gold Coast, Australien, 15/12/2008. https://doi.org/10.1007/978-3-540-92182-0_65

@inproceedings{782b6c70de4e11ddb5fc000ea68e967b,

title = "Computing the Maximum Detour of a Plane Graph in Subquadratic Time",

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.",

author = "Christian Wulff-Nilsen",

year = "2008",

doi = "10.1007/978-3-540-92182-0_65",

language = "English",

series = "Lecture notes in computer science",

publisher = "Springer",

number = "5369",

pages = "740--751",

editor = "Seok-Hee Hong and Hiroshi Nagamochi and Takuro Fukunaga",

booktitle = "Algorithms and Computation",

note = "International Symposium on Algorithms and Computation ; Conference date: 15-12-2008 Through 17-12-2008",

}

TY - GEN

T1 - Computing the Maximum Detour of a Plane Graph in Subquadratic Time

AU - Wulff-Nilsen, Christian

N1 - Conference code: 19

PY - 2008

Y1 - 2008

N2 - 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.

AB - 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.

U2 - 10.1007/978-3-540-92182-0_65

DO - 10.1007/978-3-540-92182-0_65

M3 - Article in proceedings

T3 - Lecture notes in computer science

SP - 740

EP - 751

BT - Algorithms and Computation

A2 - Hong, Seok-Hee

A2 - Nagamochi, Hiroshi

A2 - Fukunaga, Takuro

PB - Springer

T2 - International Symposium on Algorithms and Computation

Y2 - 15 December 2008 through 17 December 2008

ER -

Computing the Maximum Detour of a Plane Graph in Subquadratic Time

Abstract

Konference

Adgang til dokumentet

Fingeraftryk

Citationsformater