Computing the dilation of edge-augmented graphs in metric spaces

Publikation: Bidrag til tidsskrift › Konferenceartikel › Forskning › fagfællebedømt

Standard

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

I: Computational Geometry, Bind 43, Nr. 2, 2010, s. 68-72.

Publikation: Bidrag til tidsskrift › Konferenceartikel › Forskning › fagfællebedømt

Harvard

Wulff-Nilsen, C 2010, 'Computing the dilation of edge-augmented graphs in metric spaces', Computational Geometry, bind 43, nr. 2, s. 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. I: Computational Geometry. 2010 ; Bind 43, Nr. 2. s. 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