MPI-I-94-115
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.
-
MPI-I-94-115.pdf
- Attachement: MPI-I-94-115.ps.gz (81 KBytes); MPI-I-94-115.pdf (241 KBytes)
URL to this document: https://domino.mpi-inf.mpg.de/internet/reports.nsf/NumberView/1994-115
BibTeX
@TECHREPORT{AryaSmid94,
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},
}