Computing the dilation of edge-augmented graphs in metric spaces

Christian Wulff-Nilsen

doi:10.1016/j.comgeo.2009.03.008

Computing the dilation of edge-augmented graphs in metric spaces

Christian Wulff-Nilsen

Department of Computer Science

7 Citations (Scopus)

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⁴) running time and uses O(n²) space. We show how to improve the running time to O(n³logn) 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.

Original language	English
Journal	Computational Geometry
Volume	43
Issue number	2
Pages (from-to)	68-72
Number of pages	5
ISSN	0925-7721
DOIs	https://doi.org/10.1016/j.comgeo.2009.03.008
Publication status	Published - Feb 2010
Event	24th European Workshop on Computational Geometry - Nancy, France Duration: 18 Mar 2008 → 20 Mar 2008 Conference number: 24

Conference

Conference	24th European Workshop on Computational Geometry
Number	24
Country/Territory	France
City	Nancy
Period	18/03/2008 → 20/03/2008

Access to Document

10.1016/j.comgeo.2009.03.008

Cite this

@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",

month = feb,

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",

}

TY - GEN

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

AU - Wulff-Nilsen, Christian

N1 - Conference code: 24

PY - 2010/2

Y1 - 2010/2

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

SN - 0925-7721

VL - 43

SP - 68

EP - 72

JO - Computational Geometry

JF - Computational Geometry

IS - 2

T2 - 24th European Workshop on Computational Geometry

Y2 - 18 March 2008 through 20 March 2008

ER -

Computing the dilation of edge-augmented graphs in metric spaces

Abstract

Conference

Access to Document

Fingerprint

Cite this