Computing the dilation of edge-augmented graphs in metric spaces

Research output: Contribution to journal › Conference article › Research › peer-review

Standard

Computing the dilation of edge-augmented graphs in metric spaces. / Wulff-Nilsen, Christian.

In: Computational Geometry, Vol. 43, No. 2, 2010, p. 68-72.

Research output: Contribution to journal › Conference article › Research › peer-review

Harvard

Wulff-Nilsen, C 2010, 'Computing the dilation of edge-augmented graphs in metric spaces', Computational Geometry, vol. 43, no. 2, pp. 68-72. https://doi.org/10.1016/j.comgeo.2009.03.008

APA

Wulff-Nilsen, C. (2010). Computing the dilation of edge-augmented graphs in metric spaces. Computational Geometry, 43(2), 68-72. https://doi.org/10.1016/j.comgeo.2009.03.008

Vancouver

Wulff-Nilsen C. Computing the dilation of edge-augmented graphs in metric spaces. Computational Geometry. 2010;43(2):68-72. https://doi.org/10.1016/j.comgeo.2009.03.008

Author

Wulff-Nilsen, Christian. / Computing the dilation of edge-augmented graphs in metric spaces. In: Computational Geometry. 2010 ; Vol. 43, No. 2. pp. 68-72.

Bibtex

@inproceedings{30e9cb40659e11de8bc9000ea68e967b,
title = "Computing the dilation of edge-augmented graphs 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(n4) running time and uses O(n2) space. We show how to improve the running time to O(n3logn) while maintaining quadratic space requirement. In fact, our algorithm not only determines the best shortcut but computes the dilation of G{(u,v)} for every pair of distinct vertices u and v.",
author = "Christian Wulff-Nilsen",
year = "2010",
doi = "10.1016/j.comgeo.2009.03.008",
language = "English",
volume = "43",
pages = "68--72",
journal = "Computational Geometry",
issn = "0925-7721",
publisher = "Elsevier",
number = "2",
note = "24th European Workshop on Computational Geometry, EuroCG 2008 ; Conference date: 18-03-2008 Through 20-03-2008",

}

RIS

TY - GEN

T1 - Computing the dilation of edge-augmented graphs in metric spaces

AU - Wulff-Nilsen, Christian

N1 - Conference code: 24

PY - 2010

Y1 - 2010

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(n4) running time and uses O(n2) space. We show how to improve the running time to O(n3logn) while maintaining quadratic space requirement. In fact, our algorithm not only determines the best shortcut but computes the dilation of G{(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(n4) running time and uses O(n2) space. We show how to improve the running time to O(n3logn) while maintaining quadratic space requirement. In fact, our algorithm not only determines the best shortcut but computes the dilation of G{(u,v)} for every pair of distinct vertices u and v.

U2 - 10.1016/j.comgeo.2009.03.008

DO - 10.1016/j.comgeo.2009.03.008

M3 - Conference article

VL - 43

SP - 68

EP - 72

JO - Computational Geometry

JF - Computational Geometry

SN - 0925-7721

IS - 2

T2 - 24th European Workshop on Computational Geometry

Y2 - 18 March 2008 through 20 March 2008

ER -

ID: 12874113