Computing Best and Worst Shortcuts of Graphs Embedded in Metric Spaces

Research output: Chapter in Book/Report/Conference proceeding › Article in proceedings › Research › peer-review

Standard

Computing Best and Worst Shortcuts of Graphs Embedded in Metric Spaces. / Wulff-Nilsen, Christian; Luo, Jun.

Algorithms and Computation: 19th International Symposium, ISAAC 2008, Gold Coast, Australia, December 15-17, 2008, Proceedings. ed. / Seok-Hee Hong; Hiroshi Nagamochi; Takuro Fukunaga. Springer, 2008. p. 764-775 (Lecture notes in computer science; No. 5369).

Research output: Chapter in Book/Report/Conference proceeding › Article in proceedings › Research › peer-review

Harvard

Wulff-Nilsen, C & Luo, J 2008, Computing Best and Worst Shortcuts of Graphs Embedded in Metric Spaces. in S-H Hong, H Nagamochi & T Fukunaga (eds), Algorithms and Computation: 19th International Symposium, ISAAC 2008, Gold Coast, Australia, December 15-17, 2008, Proceedings. Springer, Lecture notes in computer science, no. 5369, pp. 764-775, International Symposium on Algorithms and Computation, Gold Coast, Australia, 15/12/2008. https://doi.org/10.1007/978-3-540-92182-0_67

APA

Wulff-Nilsen, C., & Luo, J. (2008). Computing Best and Worst Shortcuts of Graphs Embedded in Metric Spaces. In S-H. Hong, H. Nagamochi, & T. Fukunaga (Eds.), Algorithms and Computation: 19th International Symposium, ISAAC 2008, Gold Coast, Australia, December 15-17, 2008, Proceedings (pp. 764-775). Springer. Lecture notes in computer science No. 5369 https://doi.org/10.1007/978-3-540-92182-0_67

Vancouver

Wulff-Nilsen C, Luo J. Computing Best and Worst Shortcuts of Graphs Embedded in Metric Spaces. In Hong S-H, Nagamochi H, Fukunaga T, editors, Algorithms and Computation: 19th International Symposium, ISAAC 2008, Gold Coast, Australia, December 15-17, 2008, Proceedings. Springer. 2008. p. 764-775. (Lecture notes in computer science; No. 5369). https://doi.org/10.1007/978-3-540-92182-0_67

Author

Wulff-Nilsen, Christian ; Luo, Jun. / Computing Best and Worst Shortcuts of Graphs Embedded in Metric Spaces. Algorithms and Computation: 19th International Symposium, ISAAC 2008, Gold Coast, Australia, December 15-17, 2008, Proceedings. editor / Seok-Hee Hong ; Hiroshi Nagamochi ; Takuro Fukunaga. Springer, 2008. pp. 764-775 (Lecture notes in computer science; No. 5369).

Bibtex

@inproceedings{1c2bc250de5111ddb5fc000ea68e967b,
title = "Computing Best and Worst Shortcuts of Graphs Embedded in Metric Spaces",
abstract = "Given a graph embedded in a metric space, its dilation is the maximum over all distinct pairs of vertices of the ratio between their distance in the graph and the metric distance between them. Given such a graph G with n vertices and m edges and consisting of at most two connected components, we consider the problem of augmenting G with an edge such that the resulting graph has minimum dilation. We show that we can find such an edge in O((n^4*log n)/m^{0.5}) time using linear space which solves an open problem of whether a linear-space algorithm with o(n^4) running time exists. We show that O(n^2*log n) time is achievable if G is a simple path or the union of two vertex-disjoint simple paths. Finally, we show how to find an edge that maximizes the dilation of the resulting graph in O(n^3) time with O(n^2) space and in O(n^3*log n) time with linear space.",
author = "Christian Wulff-Nilsen and Jun Luo",
year = "2008",
doi = "10.1007/978-3-540-92182-0_67",
language = "English",
series = "Lecture notes in computer science",
publisher = "Springer",
number = "5369",
pages = "764--775",
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 Best and Worst Shortcuts of Graphs Embedded in Metric Spaces

AU - Wulff-Nilsen, Christian

AU - Luo, Jun

N1 - Conference code: 19

PY - 2008

Y1 - 2008

N2 - Given a graph embedded in a metric space, its dilation is the maximum over all distinct pairs of vertices of the ratio between their distance in the graph and the metric distance between them. Given such a graph G with n vertices and m edges and consisting of at most two connected components, we consider the problem of augmenting G with an edge such that the resulting graph has minimum dilation. We show that we can find such an edge in O((n^4*log n)/m^{0.5}) time using linear space which solves an open problem of whether a linear-space algorithm with o(n^4) running time exists. We show that O(n^2*log n) time is achievable if G is a simple path or the union of two vertex-disjoint simple paths. Finally, we show how to find an edge that maximizes the dilation of the resulting graph in O(n^3) time with O(n^2) space and in O(n^3*log n) time with linear space.

AB - Given a graph embedded in a metric space, its dilation is the maximum over all distinct pairs of vertices of the ratio between their distance in the graph and the metric distance between them. Given such a graph G with n vertices and m edges and consisting of at most two connected components, we consider the problem of augmenting G with an edge such that the resulting graph has minimum dilation. We show that we can find such an edge in O((n^4*log n)/m^{0.5}) time using linear space which solves an open problem of whether a linear-space algorithm with o(n^4) running time exists. We show that O(n^2*log n) time is achievable if G is a simple path or the union of two vertex-disjoint simple paths. Finally, we show how to find an edge that maximizes the dilation of the resulting graph in O(n^3) time with O(n^2) space and in O(n^3*log n) time with linear space.

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

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

M3 - Article in proceedings

T3 - Lecture notes in computer science

SP - 764

EP - 775

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 -

ID: 9617006