File Download
There are no files associated with this item.
Links for fulltext
(May Require Subscription)
- Publisher Website: 10.1145/1109557.1109566
- Scopus: eid_2-s2.0-33244489812
Supplementary
-
Citations:
- Scopus: 0
- Appears in Collections:
Conference Paper: Small hop-diameter sparse spanners for doubling metrics
Title | Small hop-diameter sparse spanners for doubling metrics |
---|---|
Authors | |
Keywords | Asymptotic Stability Function Evaluation Linear Equations Problem Solving |
Issue Date | 2006 |
Publisher | Society for Industrial and Applied Mathematics. |
Citation | Seventeenth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA '06), Miami, FL, 22-24 January 2006. In Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms, 2006, p. 70-78 How to Cite? |
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 hop diameter bounded by D if every such short path also uses at most D edges. We consider the problem of constructing sparse (1 + ε)-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 < ε < 1, one can find a (1 + ε)-spanner for the metric with nearly linear number of edges (i.e., only O(n log* n + nε -O(k)) edges) and a constant hop diameter, and also a (1 + ε)-spanner with linear number of edges (i.e., only nε -O(k) edges) which achieves a hop diameter that grows like the functional inverse of the Ackermann's function. Moreover, we prove that such tradeoffs between the number of edges and the hop diameter are asymptotically optimal. |
Persistent Identifier | http://hdl.handle.net/10722/92657 |
References |
DC Field | Value | Language |
---|---|---|
dc.contributor.author | Chan, THH | en_HK |
dc.contributor.author | Gupta, A | en_HK |
dc.date.accessioned | 2010-09-17T10:53:14Z | - |
dc.date.available | 2010-09-17T10:53:14Z | - |
dc.date.issued | 2006 | en_HK |
dc.identifier.citation | Seventeenth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA '06), Miami, FL, 22-24 January 2006. In Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms, 2006, p. 70-78 | en_HK |
dc.identifier.uri | http://hdl.handle.net/10722/92657 | - |
dc.description.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 hop diameter bounded by D if every such short path also uses at most D edges. We consider the problem of constructing sparse (1 + ε)-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 < ε < 1, one can find a (1 + ε)-spanner for the metric with nearly linear number of edges (i.e., only O(n log* n + nε -O(k)) edges) and a constant hop diameter, and also a (1 + ε)-spanner with linear number of edges (i.e., only nε -O(k) edges) which achieves a hop diameter that grows like the functional inverse of the Ackermann's function. Moreover, we prove that such tradeoffs between the number of edges and the hop diameter are asymptotically optimal. | en_HK |
dc.language | eng | en_HK |
dc.publisher | Society for Industrial and Applied Mathematics. | - |
dc.relation.ispartof | Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms | en_HK |
dc.subject | Asymptotic Stability | en_HK |
dc.subject | Function Evaluation | en_HK |
dc.subject | Linear Equations | en_HK |
dc.subject | Problem Solving | en_HK |
dc.title | Small hop-diameter sparse spanners for doubling metrics | en_HK |
dc.type | Conference_Paper | en_HK |
dc.identifier.email | Chan, THH:hubert@cs.hku.hk | en_HK |
dc.identifier.authority | Chan, THH=rp01312 | en_HK |
dc.description.nature | link_to_subscribed_fulltext | - |
dc.identifier.doi | 10.1145/1109557.1109566 | - |
dc.identifier.scopus | eid_2-s2.0-33244489812 | en_HK |
dc.relation.references | http://www.scopus.com/mlt/select.url?eid=2-s2.0-33244489812&selection=ref&src=s&origin=recordpage | en_HK |
dc.identifier.spage | 70 | en_HK |
dc.identifier.epage | 78 | en_HK |
dc.identifier.scopusauthorid | Chan, THH=12645073600 | en_HK |
dc.identifier.scopusauthorid | Gupta, A=8354044800 | en_HK |