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

Datalogisk Institut

12 Citationer (Scopus)

Abstract

Givet en graf indlejret i et metrisk rum, dens omvej (dilation) er maksimum over alle forskellige knudepar af forholdet mellem afstanden mellem dem i grafen og metrik-afstanden mellem dem. Givet en sådan graf G med n knuder og m kanter og bestående af højst to sammenhængende komponenter, betragter vi problemet med at udvide G med en kant således, at den resulterende graf har minimal omvej. Vi viser, at man kan finde en sådan kant i O((n^4*log n)/m^{0.5}) tid og lineær plads, hvilket løser et åbent problem om, hvorvidt en lineær plads-algoritme med o(n^4) køretid eksisterer. Vi viser, at O(n^2*log n) køretid kan opnås, hvis G er en simpel vej eller foreningen af to knude-disjunkte simple veje. Endelig viser vi, hvordan man kan finde en kant, der maksimerer omvejen i den resulterende graf i O(n^3) tid og O(n^2) plads og i O(n^3*log n) tid med lineær plads.

Originalsprog	Engelsk
Titel	Algorithms and Computation : 19th International Symposium, ISAAC 2008, Gold Coast, Australia, December 15-17, 2008, Proceedings
Redaktører	Seok-Hee Hong, Hiroshi Nagamochi, Takuro Fukunaga
Antal sider	12
Forlag	Springer
Publikationsdato	2008
Sider	764-775
ISBN (Elektronisk)	978-3-540-92181-3
DOI	https://doi.org/10.1007/978-3-540-92182-0_67
Status	Udgivet - 2008
Begivenhed	International Symposium on Algorithms and Computation - Gold Coast, Australien Varighed: 15 dec. 2008 → 17 dec. 2008 Konferencens nummer: 19

Konference

Konference	International Symposium on Algorithms and Computation
Nummer	19
Land/Område	Australien
By	Gold Coast
Periode	15/12/2008 → 17/12/2008

Navn	Lecture notes in computer science
Nummer	5369
ISSN	0302-9743

Adgang til dokumentet

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

Citationsformater

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. red. / Seok-Hee Hong; Hiroshi Nagamochi; Takuro Fukunaga. Springer, 2008. s. 764-775 (Lecture notes in computer science; Nr. 5369).

Publikation: Bidrag til bog/antologi/rapport › Konferencebidrag i proceedings › Forskning › peer review

Wulff-Nilsen, C & Luo, J 2008, Computing Best and Worst Shortcuts of Graphs Embedded in Metric Spaces. 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. 764-775, International Symposium on Algorithms and Computation, Gold Coast, Australien, 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. I Hong SH, Nagamochi H, Fukunaga T, red., Algorithms and Computation: 19th International Symposium, ISAAC 2008, Gold Coast, Australia, December 15-17, 2008, Proceedings. Springer. 2008. s. 764-775. (Lecture notes in computer science; Nr. 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. red. / Seok-Hee Hong ; Hiroshi Nagamochi ; Takuro Fukunaga. Springer, 2008. s. 764-775 (Lecture notes in computer science; Nr. 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

Konference

Adgang til dokumentet

Fingeraftryk

Citationsformater