Improving the stretch factor of a geometric network by edge augmentation

M. Farshi, P. Giannopoulos, J. Gudmundsson

Onderzoeksoutput: Bijdrage aan tijdschriftTijdschriftartikelAcademicpeer review

26 Citaten (Scopus)
218 Downloads (Pure)


Given a Euclidean graph $G$ in $\mathbb{R}^d$ with $n$ vertices and $m$ edges, we consider the problem of adding an edge to $G$ such that the stretch factor of the resulting graph is minimized. Currently, the fastest algorithm for computing the stretch factor of a graph with positive edge weights runs in $\cal{O}$$(nm+n^2 \log n)$ time, resulting in a trivial $\cal{O}$$(n^3m+n^4 \log n)$-time algorithm for computing the optimal edge. First, we show that a simple modification yields the optimal solution in $\cal{O}$$(n^4)$ time using $\cal{O}$$(n^2)$ space. To reduce the running time we consider several approximation algorithms.
Originele taal-2Engels
Pagina's (van-tot)226-240
TijdschriftSIAM Journal on Computing
Nummer van het tijdschrift1
StatusGepubliceerd - 2008


Duik in de onderzoeksthema's van 'Improving the stretch factor of a geometric network by edge augmentation'. Samen vormen ze een unieke vingerafdruk.

Citeer dit