GGV11
Summary
Gavoille, Cyril, Godfroy, Quentin and Viennot, Laurent (2011) Node-Disjoint Multipath Spanners and their Relationship with Fault-Tolerant Spanners. In 15th International Conference on Principles of Distributed Systems (OPODIS). Toulouse, France, dec. Springer, pages 143-158. ((URL)) (PDF)
Abstract
Motivated by multipath routing, we introduce a multi-connected variant of spanners. For that purpose we introduce the {$p$}-multipath cost between two nodes {$u$} and {$v$} as the minimum weight of a collection of {$p$} internally vertex-disjoint paths between {$u$} and {$v$}. Given a weighted graph {$G$}, a subgraph {$H$} is a {$p$}-multipath {$s$}-spanner if for all {$u,v$}, the {$p$}-multipath cost between {$u$} and {$v$} in {$H$} is at most {$s$} times the {$p$}-multipath cost in {$G$}. The {$s$} factor is called the stretch.\\ Building upon recent results on fault-tolerant spanners, we show how to build {$p$}-multipath spanners of constant stretch and of {$\tilde{O}(n^{1+1/k})$} edges, for fixed parameters {$p$} and {$k$}, {$n$} being the number of nodes of the graph. Such spanners can be constructed by a distributed algorithm running in {$O(k)$} rounds.\\ Additionally, we give an improved construction for the case {$p=k=2$}. Our spanner {$H$} has {$O(n^{3/2})$} edges and the {$p$}-multipath cost in {$H$} between any two node is at most twice the corresponding one in {$G$} plus {$O(W)$}, {$W$} being the maximum edge weight.
Bibtex entry
@INPROCEEDINGS { GGV11,
AUTHOR = { Gavoille, Cyril and Godfroy, Quentin and Viennot, Laurent },
TITLE = { Node-Disjoint Multipath Spanners and their Relationship with Fault-Tolerant Spanners },
BOOKTITLE = { 15th International Conference on Principles of Distributed Systems (OPODIS) },
PUBLISHER = { Springer },
ADDRESS = { Toulouse, France },
VOLUME = { 7109 },
SERIES = { Lecture Notes in Computer Science },
PAGES = { 143-158 },
MONTH = { dec },
YEAR = { 2011 },
KEYWORDS = { spanner },
URL = { http://dx.doi.org/10.1007/978-3-642-25873-2_11 },
PDF = { http://arxiv.org/pdf/1109.2696v2 },
ABSTRACT = { Motivated by multipath routing, we introduce a multi-connected variant of spanners. For that purpose we introduce the {$p$}-multipath cost between two nodes {$u$} and {$v$} as the minimum weight of a collection of {$p$} internally vertex-disjoint paths between {$u$} and {$v$}. Given a weighted graph {$G$}, a subgraph {$H$} is a {$p$}-multipath {$s$}-spanner if for all {$u,v$}, the {$p$}-multipath cost between {$u$} and {$v$} in {$H$} is at most {$s$} times the {$p$}-multipath cost in {$G$}. The {$s$} factor is called the stretch.\\ Building upon recent results on fault-tolerant spanners, we show how to build {$p$}-multipath spanners of constant stretch and of {$\tilde{O}(n^{1+1/k})$} edges, for fixed parameters {$p$} and {$k$}, {$n$} being the number of nodes of the graph. Such spanners can be constructed by a distributed algorithm running in {$O(k)$} rounds.\\ Additionally, we give an improved construction for the case {$p=k=2$}. Our spanner {$H$} has {$O(n^{3/2})$} edges and the {$p$}-multipath cost in {$H$} between any two node is at most twice the corresponding one in {$G$} plus {$O(W)$}, {$W$} being the maximum edge weight. },
}