Finding the best shortcut in a geometric network

M. Farshi; P. Giannopoulos; J. Gudmundsson

Finding the best shortcut in a geometric network

M. Farshi, P. Giannopoulos, J. Gudmundsson

Algorithms

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic

Abstract

Given a Euclidean graph G in Rd with n vertices and m edges we consider the problem of adding a shortcut such that the stretch factor of the resulting graph is minimized. Currently, the fastest algorithm for computing the stretch factor of a Euclidean graph runs in O(mn + n2 log n) time, resulting in a trivial O(mn3 + n4 log n) time algorithm for computing the optimal shortcut. First, we show that a simple modification yields the optimal solution in O(n4) time using O(n2) space. To reduce the running times we consider several approximation algorithms. Our main result is a (2+e)-approximation algorithm with running time O(nm + n2(log n + 1/e3d)) using O(n2) space.

Original language	English
Title of host publication	Abstracts 21th European Workshop on Computational Geometry (EWCG 2005, Eindhoven, The Netherlands, March 9-11, 2005)
Editors	M.T. Berg, de
Pages	29-32
Publication status	Published - 2005

Cite this

@inproceedings{121adbb829e54c3a9b22a272bd4e814c,

title = "Finding the best shortcut in a geometric network",

abstract = "Given a Euclidean graph G in Rd with n vertices and m edges we consider the problem of adding a shortcut such that the stretch factor of the resulting graph is minimized. Currently, the fastest algorithm for computing the stretch factor of a Euclidean graph runs in O(mn + n2 log n) time, resulting in a trivial O(mn3 + n4 log n) time algorithm for computing the optimal shortcut. First, we show that a simple modification yields the optimal solution in O(n4) time using O(n2) space. To reduce the running times we consider several approximation algorithms. Our main result is a (2+e)-approximation algorithm with running time O(nm + n2(log n + 1/e3d)) using O(n2) space.",

author = "M. Farshi and P. Giannopoulos and J. Gudmundsson",

year = "2005",

language = "English",

pages = "29--32",

editor = "{Berg, de}, M.T.",

booktitle = "Abstracts 21th European Workshop on Computational Geometry (EWCG 2005, Eindhoven, The Netherlands, March 9-11, 2005)",

}

TY - GEN

T1 - Finding the best shortcut in a geometric network

AU - Farshi, M.

AU - Giannopoulos, P.

AU - Gudmundsson, J.

PY - 2005

Y1 - 2005

N2 - Given a Euclidean graph G in Rd with n vertices and m edges we consider the problem of adding a shortcut such that the stretch factor of the resulting graph is minimized. Currently, the fastest algorithm for computing the stretch factor of a Euclidean graph runs in O(mn + n2 log n) time, resulting in a trivial O(mn3 + n4 log n) time algorithm for computing the optimal shortcut. First, we show that a simple modification yields the optimal solution in O(n4) time using O(n2) space. To reduce the running times we consider several approximation algorithms. Our main result is a (2+e)-approximation algorithm with running time O(nm + n2(log n + 1/e3d)) using O(n2) space.

AB - Given a Euclidean graph G in Rd with n vertices and m edges we consider the problem of adding a shortcut such that the stretch factor of the resulting graph is minimized. Currently, the fastest algorithm for computing the stretch factor of a Euclidean graph runs in O(mn + n2 log n) time, resulting in a trivial O(mn3 + n4 log n) time algorithm for computing the optimal shortcut. First, we show that a simple modification yields the optimal solution in O(n4) time using O(n2) space. To reduce the running times we consider several approximation algorithms. Our main result is a (2+e)-approximation algorithm with running time O(nm + n2(log n + 1/e3d)) using O(n2) space.

UR - http://www.win.tue.nl/EWCG2005/Proceedings/8.pdf

M3 - Conference contribution

SP - 29

EP - 32

BT - Abstracts 21th European Workshop on Computational Geometry (EWCG 2005, Eindhoven, The Netherlands, March 9-11, 2005)

A2 - Berg, de, M.T.

ER -

Finding the best shortcut in a geometric network

Abstract

Other files and links

Fingerprint

Cite this