Standard
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 › fagfællebedømt
Harvard
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
APA
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 (s. 740-751). Springer. Lecture notes in computer science Nr. 5369
https://doi.org/10.1007/978-3-540-92182-0_65
Vancouver
Wulff-Nilsen C.
Computing the Maximum Detour of a Plane Graph in Subquadratic Time. I Hong S-H, Nagamochi H, Fukunaga T, red., Algorithms and Computation: 19th International Symposium, ISAAC 2008, Gold Coast, Australia, December 15-17, 2008, Proceedings. Springer. 2008. s. 740-751. (Lecture notes in computer science; Nr. 5369).
https://doi.org/10.1007/978-3-540-92182-0_65
Author
Wulff-Nilsen, Christian. / Computing the Maximum Detour of a Plane Graph in Subquadratic Time. 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).
Bibtex
@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",
address = "Switzerland",
note = "null ; Conference date: 15-12-2008 Through 17-12-2008",
}
RIS
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
Y2 - 15 December 2008 through 17 December 2008
ER -
