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

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

Standard

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. ed. / Sylvain Petitjean. LORIA, Nancy, France, 2008. p. 123-126.

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

Harvard

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

APA

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

Vancouver

Wulff-Nilsen C. Computing the Dilation of Edge-Augmented Graphs Embedded in Metric Spaces. In Petitjean S, editor, Collection of Abstracts of the 24th European Workshop on Computational Geometry: EuroCG, LORIA, Nancy, France, March 18-20, 2008. LORIA, Nancy, France. 2008. p. 123-126

Author

Wulff-Nilsen, Christian. / Computing the Dilation of Edge-Augmented Graphs Embedded in Metric Spaces. Collection of Abstracts of the 24th European Workshop on Computational Geometry: EuroCG, LORIA, Nancy, France, March 18-20, 2008. editor / Sylvain Petitjean. LORIA, Nancy, France, 2008. pp. 123-126

Bibtex

@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 = "null ; Conference date: 18-03-2008 Through 20-03-2008",

}

RIS

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

Y2 - 18 March 2008 through 20 March 2008

ER -

ID: 9617833