de.mpg.escidoc.pubman.appbase.FacesBean
Deutsch
 
Hilfe Wegweiser Impressum Kontakt Einloggen
  DetailsucheBrowse

Datensatz

DATENSATZ AKTIONENEXPORT

Freigegeben

Bericht

Efficient construction of a bounded degree spanner with low weight

MPG-Autoren
http://pubman.mpdl.mpg.de/cone/persons/resource/persons44034

Arya,  Sunil
Algorithms and Complexity, MPI for Informatics, Max Planck Society;

http://pubman.mpdl.mpg.de/cone/persons/resource/persons45509

Smid,  Michiel
Algorithms and Complexity, MPI for Informatics, Max Planck Society;

Externe Ressourcen
Es sind keine Externen Ressourcen verfügbar
Volltexte (frei zugänglich)

MPI-I-94-115.pdf
(beliebiger Volltext), 241KB

Ergänzendes Material (frei zugänglich)
Es sind keine frei zugänglichen Ergänzenden Materialien verfügbar
Zitation

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.


Zitierlink: http://hdl.handle.net/11858/00-001M-0000-0014-B518-6
Zusammenfassung
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.