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

Datalogisk Institut

7 Citationer (Scopus)

Abstract

Lad G=(V,E) være en ikke-orienteret graf med n knuder indlejret i et metrisk rum. Betragt følgende problem: tilføj en kant til G, som minimerer den længste omvej i den resulterende graf. Den hurtigste algoritme for dette problem har O(n⁴) køretid og bruger O(n²) plads. Vi forbedrer køretiden til O(n³logn) uden at øge pladsforbruget.
Faktisk finder vores algoritme den længste omvej i G union or logical sum

{(u,v)} for alle par af forskellige knuder u og v.
Udgivelsesdato: 23/6-2009

Originalsprog	Engelsk
Tidsskrift	Computational Geometry
Vol/bind	43
Udgave nummer	2
Sider (fra-til)	68-72
Antal sider	5
ISSN	0925-7721
DOI	https://doi.org/10.1016/j.comgeo.2009.03.008
Status	Udgivet - feb. 2010
Begivenhed	24th European Workshop on Computational Geometry - Nancy, Frankrig Varighed: 18 mar. 2008 → 20 mar. 2008 Konferencens nummer: 24

Konference

Konference	24th European Workshop on Computational Geometry
Nummer	24
Land/Område	Frankrig
By	Nancy
Periode	18/03/2008 → 20/03/2008

Adgang til dokumentet

10.1016/j.comgeo.2009.03.008

Citationsformater

@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

Konference

Adgang til dokumentet

Fingeraftryk

Citationsformater