# Item

ITEM ACTIONSEXPORT

Released

Report

#### Efficient construction of a bounded degree spanner with low weight

##### MPS-Authors

##### Locator

There are no locators available

##### Fulltext (public)

MPI-I-94-115.pdf

(Any fulltext), 241KB

##### Supplementary Material (public)

There is no public supplementary material available

##### Citation

Arya, S., & Smid, M.(1994). *Efficient construction of a
bounded degree spanner with low weight* (MPI-I-94-115). Saarbrücken: Max-Planck-Institut für Informatik.

Cite as: http://hdl.handle.net/11858/00-001M-0000-0014-B518-6

##### Abstract

Let $S$ be a set of $n$ points in $\IR^d$ and let $t>1$ be
a real number. A $t$-spanner for $S$ is a graph having the
points of $S$ as its vertices such that for any pair $p,q$ of
points there is a path between them of length at most $t$
times the euclidean distance between $p$ and $q$.
An efficient implementation of a greedy algorithm is given
that constructs a $t$-spanner having bounded degree such
that the total length of all its edges is bounded by
$O(\log n)$ times the length of a minimum spanning tree
for $S$. The algorithm has running time $O(n \log^d n)$.
Also, an application to the problem of distance enumeration
is given.