# 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. },}