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 Library locked




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

Journal Title*:

Discrete and Computational Geometry

Journal's URL:

http://www.springerlink.com/content/100356/

Download URL
for the article:

http://www.springerlink.com/content/f85007822x456285/fulltext.pdf

Language:

English

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, Abstract, ©

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},
ADDRESS = {New York, NY},
MONTH = {January},
ISBN = {0179-5376},
DOI = {10.1007/s00454-008-9115-5},
}


Entry last modified by Anja Becker, 03/04/2010
Show details for Edit History (please click the blue arrow to see the details)Edit History (please click the blue arrow to see the details)
Hide details for Edit History (please click the blue arrow to see the details)Edit History (please click the blue arrow to see the details)

Editor(s)
[Library]
Created
01/14/2009 04:53:50 PM
Revisions
2.
1.
0.

Editor(s)
Anja Becker
Hubert Chan
Hubert Chan

Edit Dates
04.03.2010 11:41:17
01/14/2009 04:56:15 PM
01/14/2009 04:53:50 PM

Show details for Attachment SectionAttachment Section
Hide details for Attachment SectionAttachment Section