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. red. / Sylvain Petitjean. LORIA, Nancy, France, 2008. s. 123-126.
Publikation: Bidrag til bog/antologi/rapport › Konferencebidrag i proceedings › Forskning › fagfællebedømt
Harvard
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>
APA
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 (s. 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. I Petitjean S, red., Collection of Abstracts of the 24th European Workshop on Computational Geometry: EuroCG, LORIA, Nancy, France, March 18-20, 2008. LORIA, Nancy, France. 2008. s. 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. red. / Sylvain Petitjean. LORIA, Nancy, France, 2008. s. 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 -
