Sparse Spanners vs. Compact Routing
| hal.structure.identifier | Laboratoire Bordelais de Recherche en Informatique [LaBRI] | |
| hal.structure.identifier | Algorithmics for computationally intensive applications over wide scale distributed platforms [CEPAGE] | |
| hal.structure.identifier | Institut universitaire de France [IUF] | |
| dc.contributor.author | GAVOILLE, Cyril | |
| hal.structure.identifier | Massachusetts Institute of Technology [MIT] | |
| dc.contributor.author | CHRISITAN, Sommer | |
| dc.date.accessioned | 2024-04-15T09:46:19Z | |
| dc.date.available | 2024-04-15T09:46:19Z | |
| dc.date.issued | 2011-06 | |
| dc.date.conference | 2011-06 | |
| dc.identifier.uri | https://oskar-bordeaux.fr/handle/20.500.12278/197993 | |
| dc.description.abstractEn | Routing with \emph{multiplicative} stretch~$3$ (which means that the path used by the routing scheme can be up to three times longer than a shortest path) can be done with routing tables of $\tTheta(\sqrt{n}\,)$~bits\footnote{Tilde-big-$O$ notation is similar to big-$O$ notation up to factors poly-logarithmic in $n$.} per node. The space lower bound is due to the existence of dense graphs with large girth. Dense graphs can be sparsified to subgraphs, called \emph{spanners}, with various stretch guarantees. There are spanners with \emph{additive} stretch guarantees (some even have constant additive stretch) but only very few additive routing schemes are known. In this paper, we give reasons why routing in unweighted graphs with \emph{additive} stretch is difficult in the form of space lower bounds for general graphs and for planar graphs. We prove that any routing scheme using routing tables of size $\mem$~bits per node and addresses of poly-logarithmic length has additive stretch $\tOmega(\sqrt{n/\mem}\,)$ for general graphs, and $\tOmega(\sqrt{n}/\mem)$ for planar graphs, respectively. Routing with tables of size $\tO(n^{1/3})$ thus requires a polynomial additive stretch of $\tOmega(n^{1/3})$, whereas spanners with average degree $O(n^{1/3})$ and {\em constant} additive stretch exist for all graphs. Spanners, however sparse they are, do not tell us how to route. These bounds provide the first separation of sparse spanner problems and compact routing problems. On the positive side, we give an almost tight upper bound: we present the first non-trivial compact routing scheme with $o(\lg^2 n)$-bit addresses, {\em additive} stretch $\tO(n^{1/3})$, and table size $\tO(n^{1/3})$~bits for all graphs with linear local tree-width such as planar, bounded-genus, and apex-minor-free graphs. | |
| dc.language.iso | en | |
| dc.publisher | ACM | |
| dc.source.title | $23^{rd}$ Annual ACM Symposium on Parallel Algorithms and Architectures (SPAA) | |
| dc.subject.en | Network Architecture and Design | |
| dc.subject.en | Routing protocols | |
| dc.subject.en | Routing and layout | |
| dc.subject.en | Graph Theory | |
| dc.subject.en | Graph labeling | |
| dc.subject.en | Graph algorithms | |
| dc.title | Sparse Spanners vs. Compact Routing | |
| dc.type | Communication dans un congrès | |
| dc.identifier.doi | 10.1145/1989493.1989526 | |
| dc.subject.hal | Informatique [cs]/Algorithme et structure de données [cs.DS] | |
| bordeaux.page | 225-234 | |
| bordeaux.hal.laboratories | Laboratoire Bordelais de Recherche en Informatique (LaBRI) - UMR 5800 | * |
| bordeaux.institution | Université de Bordeaux | |
| bordeaux.institution | Bordeaux INP | |
| bordeaux.institution | CNRS | |
| bordeaux.conference.title | $23^{rd}$ Annual ACM Symposium on Parallel Algorithms and Architectures (SPAA) | |
| bordeaux.country | US | |
| bordeaux.title.proceeding | $23^{rd}$ Annual ACM Symposium on Parallel Algorithms and Architectures (SPAA) | |
| bordeaux.conference.city | San Jose | |
| bordeaux.peerReviewed | oui | |
| hal.identifier | hal-00651836 | |
| hal.version | 1 | |
| hal.invited | non | |
| hal.proceedings | oui | |
| hal.popular | non | |
| hal.audience | Internationale | |
| hal.origin.link | https://hal.archives-ouvertes.fr//hal-00651836v1 | |
| bordeaux.COinS | ctx_ver=Z39.88-2004&rft_val_fmt=info:ofi/fmt:kev:mtx:journal&rft.title=Sparse%20Spanners%20vs.%20Compact%20Routing&rft.btitle=$23%5E%7Brd%7D$%20Annual%20ACM%20Symposium%20on%20Parallel%20Algorithms%20and%20Architectures%20(SPAA)&rft.atitle=Sparse%20Spanners%20vs.%20Compact%20Routing&rft.date=2011-06&rft.spage=225-234&rft.epage=225-234&rft.au=GAVOILLE,%20Cyril&CHRISITAN,%20Sommer&rft.genre=unknown |
Files in this item
| Files | Size | Format | View |
|---|---|---|---|
|
There are no files associated with this item. |
|||