Computing Best and Worst Shortcuts of Graphs Embedded in Metric Spaces

Christian Wulff-Nilsen; Jun Luo

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

Computing Best and Worst Shortcuts of Graphs Embedded in Metric Spaces

Christian Wulff-Nilsen, Jun Luo

Department of Computer Science

12 Citations (Scopus)

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.

Original language	English
Title of host publication	Algorithms and Computation : 19th International Symposium, ISAAC 2008, Gold Coast, Australia, December 15-17, 2008, Proceedings
Editors	Seok-Hee Hong, Hiroshi Nagamochi, Takuro Fukunaga
Number of pages	12
Publisher	Springer
Publication date	2008
Pages	764-775
ISBN (Electronic)	978-3-540-92181-3
DOIs	https://doi.org/10.1007/978-3-540-92182-0_67
Publication status	Published - 2008
Event	International Symposium on Algorithms and Computation - Gold Coast, Australia Duration: 15 Dec 2008 → 17 Dec 2008 Conference number: 19

Conference

Conference	International Symposium on Algorithms and Computation
Number	19
Country/Territory	Australia
City	Gold Coast
Period	15/12/2008 → 17/12/2008

Series	Lecture notes in computer science
Number	5369
ISSN	0302-9743

Access to Document

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

Cite this

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

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

Wulff-Nilsen C, Luo J. Computing Best and Worst Shortcuts of Graphs Embedded in Metric Spaces. In Hong SH, 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). doi: 10.1007/978-3-540-92182-0_67

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

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

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

}

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

T2 - International Symposium on Algorithms and Computation

Y2 - 15 December 2008 through 17 December 2008

ER -

Computing Best and Worst Shortcuts of Graphs Embedded in Metric Spaces

Abstract

Conference

Access to Document

Fingerprint

Cite this