Computing the dilation of edge-augmented graphs in metric spaces

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: Theory and Applications

JF - Computational Geometry: Theory and Applications

IS - 2

T2 - 24th European Workshop on Computational Geometry

Y2 - 18 March 2008 through 20 March 2008

ER -