Journal Article @Article Artikel in Fachzeitschrift
 Show entries of: this year (2019) | last year (2018) | two years ago (2017) | Notes URL
 Action: login to update Options: Library locked Goto entry point

 Author, Editor(s)
 Author(s): Chan, T.-H. Hubert Gupta, Anupam dblp dblp Not MPG Author(s): Gupta, Anupam
 BibTeX cite key*: ChanGupta2009

 Title
 Title*: Small Hop-diameter Sparse Spanners for Doubling Metrics

 Journal

 Publisher
 Publisher's Name: Springer Publisher's URL: http://www.springer-ny.com/ Publisher's Address: New York, NY ISSN: 0179-5376

 Vol, No, pp, Date
 Volume*: 41 Number: 1 Publishing Date: January 2009 Pages*: 28-44 Number of VG Pages: Page Start: 28 Page End: 44 Sequence Number: DOI: 10.1007/s00454-008-9115-5

 Note: (LaTeX) Abstract: Given a metric $M = (V,d)$, a graph $G = (V,E)$ is a $t$-spanner for $M$ if every pair of nodes in $V$ has a short'' path (i.e., of length at most $t$ times their actual distance) between them in the spanner. Furthermore, this spanner has a \emph{hop diameter} bounded by $D$ if every pair of nodes has such a short path that also uses at most $D$ edges. We consider the problem of constructing sparse $(1+\eps)$-spanners with small hop diameter for metrics of low doubling dimension. In this paper, we show that given any metric with constant doubling dimension $k$, and any $0 < \eps < 1$, one can find $(1 + \eps)$-spanner for the metric with nearly linear number of edges (i.e., only $O(n \log^* n + n\eps^{-O(k)})$ edges) and \emph{constant} hop diameter; we can also obtain a $(1 + \eps)$-spanner with linear number of edges (i.e., only $n\eps^{-O(k)}$ edges) that achieves a hop diameter that grows like the functional inverse of Ackermann's function. Moreover, we prove that such tradeoffs between the number of edges and the hop diameter are asymptotically optimal. URL for the Abstract: Categories, Keywords: Algorithms, Sparse spanners, Doubling metrics, Hop diameter HyperLinks / References / URLs: Copyright Message: © The Author(s) 2008. This article is published with open access at Springerlink.com Personal Comments: Download Access Level: Public

 Correlation
 MPG Unit: Max-Planck-Institut für Informatik MPG Subunit: Algorithms and Complexity Group Appearance: MPII WWW Server, MPII FTP Server, MPG publications list, university publications list, working group publication list, Fachbeirat, VG Wort

BibTeX Entry:

@ARTICLE{ChanGupta2009,
AUTHOR = {Chan, T.-H. Hubert and Gupta, Anupam},
TITLE = {Small Hop-diameter Sparse Spanners for Doubling Metrics},
JOURNAL = {Discrete and Computational Geometry},
PUBLISHER = {Springer},
YEAR = {2009},
NUMBER = {1},
VOLUME = {41},
PAGES = {28--44},