Computing the Dilation of Edge-Augmented Graphs Embedded in Metric Spaces

Christian Wulff-Nilsen

Computing the Dilation of Edge-Augmented Graphs Embedded in Metric Spaces

Datalogisk Institut

Abstract

Lad G = (V,E) være en ikke-orienteret graf med n knuder indlejret i et metrisk rum. Vi betragter problemet med at finde en shortcut-kant i G, der minimerer omvejen (dilation) af den resulterende graf. Den hurtigste algoritme for dette problem har O(n^4) køretid og bruger O(n^2) plads. Vi viser, hvordan køretiden kan forbedres til O(n^3*log n) med samme pladsforbrug. Vores algoritme finder ikke kun det bedste shortcut, men bestemmer omvejen af G U {(u,v)} for alle par af forskellige knuder u og v.

Originalsprog	Engelsk
Titel	Collection of Abstracts of the 24th European Workshop on Computational Geometry : EuroCG, LORIA, Nancy, France, March 18-20, 2008
Redaktører	Sylvain Petitjean
Antal sider	4
Forlag	LORIA, Nancy, France
Publikationsdato	2008
Sider	123-126
Status	Udgivet - 2008
Begivenhed	European Workshop on Computational Geometry (EuroCG) - Nancy, Frankrig Varighed: 18 mar. 2008 → 20 mar. 2008 Konferencens nummer: 24

Konference

Konference	European Workshop on Computational Geometry (EuroCG)
Nummer	24
Land/Område	Frankrig
By	Nancy
Periode	18/03/2008 → 20/03/2008

Adgang til dokumentet

http://eurocg08.loria.fr/EuroCG08Abstracts.pdf

Citationsformater

Computing the Dilation of Edge-Augmented Graphs Embedded in Metric Spaces. / Wulff-Nilsen, Christian.

Collection of Abstracts of the 24th European Workshop on Computational Geometry: EuroCG, LORIA, Nancy, France, March 18-20, 2008. red. / Sylvain Petitjean. LORIA, Nancy, France, 2008. s. 123-126.

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

Wulff-Nilsen, C 2008, Computing the Dilation of Edge-Augmented Graphs Embedded in Metric Spaces. i S Petitjean (red.), Collection of Abstracts of the 24th European Workshop on Computational Geometry: EuroCG, LORIA, Nancy, France, March 18-20, 2008. LORIA, Nancy, France, s. 123-126, European Workshop on Computational Geometry (EuroCG), Nancy, Frankrig, 18/03/2008. <http://eurocg08.loria.fr/EuroCG08Abstracts.pdf>

@inproceedings{07889180de5511ddb5fc000ea68e967b,

title = "Computing the Dilation of Edge-Augmented Graphs Embedded in Metric Spaces",

abstract = "Let G = (V,E) be an undirected graph with n vertices embedded in a metric space. We consider the problem of adding a shortcut edge in G that minimizes the dilation of the resulting graph. The fastest algorithm to date for this problem has O(n^4) running time and uses O(n^2) space. We show how to improve running time to O(n^3*log n) while maintaining quadratic space requirement. In fact, our algorithm not only determines the best shortcut but computes the dilation of G U {(u,v)} for every pair of distinct vertices u and v.",

author = "Christian Wulff-Nilsen",

year = "2008",

language = "English",

pages = "123--126",

editor = "Sylvain Petitjean",

booktitle = "Collection of Abstracts of the 24th European Workshop on Computational Geometry",

publisher = "LORIA, Nancy, France",

note = "European Workshop on Computational Geometry (EuroCG) ; Conference date: 18-03-2008 Through 20-03-2008",

}

TY - GEN

T1 - Computing the Dilation of Edge-Augmented Graphs Embedded in Metric Spaces

AU - Wulff-Nilsen, Christian

N1 - Conference code: 24

PY - 2008

Y1 - 2008

N2 - Let G = (V,E) be an undirected graph with n vertices embedded in a metric space. We consider the problem of adding a shortcut edge in G that minimizes the dilation of the resulting graph. The fastest algorithm to date for this problem has O(n^4) running time and uses O(n^2) space. We show how to improve running time to O(n^3*log n) while maintaining quadratic space requirement. In fact, our algorithm not only determines the best shortcut but computes the dilation of G U {(u,v)} for every pair of distinct vertices u and v.

AB - Let G = (V,E) be an undirected graph with n vertices embedded in a metric space. We consider the problem of adding a shortcut edge in G that minimizes the dilation of the resulting graph. The fastest algorithm to date for this problem has O(n^4) running time and uses O(n^2) space. We show how to improve running time to O(n^3*log n) while maintaining quadratic space requirement. In fact, our algorithm not only determines the best shortcut but computes the dilation of G U {(u,v)} for every pair of distinct vertices u and v.

M3 - Article in proceedings

SP - 123

EP - 126

BT - Collection of Abstracts of the 24th European Workshop on Computational Geometry

A2 - Petitjean, Sylvain

PB - LORIA, Nancy, France

T2 - European Workshop on Computational Geometry (EuroCG)

Y2 - 18 March 2008 through 20 March 2008

ER -

Computing the Dilation of Edge-Augmented Graphs Embedded in Metric Spaces

Abstract

Konference

Adgang til dokumentet

Fingeraftryk

Citationsformater