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

}