MPI-INF/SWS Research Reports 1991-2021

2. Number - All Departments


Efficient construction of a bounded degree spanner with low weight

Arya, Sunil and Smid, Michiel

April 1994, 25 pages.

Status: available - back from printing

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.

  • Attachement: (81 KBytes); MPI-I-94-115.pdf (241 KBytes)

URL to this document:

Hide details for BibTeXBibTeX
  AUTHOR = {Arya, Sunil and Smid, Michiel},
  TITLE = {Efficient construction of a bounded degree spanner with low weight},
  TYPE = {Research Report},
  INSTITUTION = {Max-Planck-Institut f{\"u}r Informatik},
  ADDRESS = {Im Stadtwald, D-66123 Saarbr{\"u}cken, Germany},
  NUMBER = {MPI-I-94-115},
  MONTH = {April},
  YEAR = {1994},
  ISSN = {0946-011X},