Computing the Maximum Detour of a Plane Graph in Subquadratic Time

Publikation: Working paperForskning

Standard

Computing the Maximum Detour of a Plane Graph in Subquadratic Time. / Wulff-Nilsen, Christian.

København : Department of Computer Science, University of Copenhagen, 2008.

Publikation: Working paperForskning

Harvard

Wulff-Nilsen, C 2008 'Computing the Maximum Detour of a Plane Graph in Subquadratic Time' Department of Computer Science, University of Copenhagen, København.

APA

Wulff-Nilsen, C. (2008). Computing the Maximum Detour of a Plane Graph in Subquadratic Time. København: Department of Computer Science, University of Copenhagen.

Vancouver

Wulff-Nilsen C. Computing the Maximum Detour of a Plane Graph in Subquadratic Time. København: Department of Computer Science, University of Copenhagen. 2008.

Author

Wulff-Nilsen, Christian. / Computing the Maximum Detour of a Plane Graph in Subquadratic Time. København : Department of Computer Science, University of Copenhagen, 2008.

Bibtex

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

}

RIS

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 -

ID: 9618113