Computing the Maximum Detour of a Plane Graph in Subquadratic Time

Christian Wulff-Nilsen

Computing the Maximum Detour of a Plane Graph in Subquadratic Time

Christian Wulff-Nilsen

Datalogisk Institut

3 Citationer (Scopus)

657 Downloads (Pure)

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 alle par af forskellige punkter p og q i G (knuder såvel som indre punkter i kanter) af forholdet mellem afstanden mellem p og q i G og afstanden |pq|. Den hurtigste algoritme for dette problem har O(n^2) køretid, hvor n er antallet af knuder i G. 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 dens maksimale omvej bestemmes i O(n(log n)^3) forventet tid.

Originalsprog	Engelsk
Udgivelsessted	København
Udgiver	Department of Computer Science, University of Copenhagen
Antal sider	25
Status	Udgivet - 2008

Adgang til dokumentet

08-07-WULLF-NILSENForlagets udgivne version, 298 KB

Citationsformater

@techreport{7c38c840de5711ddb5fc000ea68e967b,

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 O(n^2) running time. 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",

language = "English",

publisher = "Department of Computer Science, University of Copenhagen",

type = "WorkingPaper",

institution = "Department of Computer Science, University of Copenhagen",

}

TY - UNPB

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

AU - Wulff-Nilsen, Christian

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 O(n^2) running time. 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 O(n^2) running time. 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.

M3 - Working paper

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

PB - Department of Computer Science, University of Copenhagen

CY - København

ER -

Computing the Maximum Detour of a Plane Graph in Subquadratic Time

Abstract

Adgang til dokumentet

Fingeraftryk

Citationsformater