Multipath Spanners

Cyril Gavoille 1, 2, 3 Quentin Godfroy 1 Laurent Viennot 4, 5
2 CEPAGE - Algorithmics for computationally intensive applications over wide scale distributed platforms
Université Sciences et Technologies - Bordeaux 1, Inria Bordeaux - Sud-Ouest, École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB), CNRS - Centre National de la Recherche Scientifique : UMR5800
5 GANG - Networks, Graphs and Algorithms
LIAFA - Laboratoire d'informatique Algorithmique : Fondements et Applications, Inria Paris-Rocquencourt
Abstract : This paper concerns graph spanners that approximate multipaths between pair of vertices of an undirected graphs with $n$ vertices. Classically, a spanner $H$ of stretch $s$ for a graph $G$ is a spanning subgraph such that the distance in $H$ between any two vertices is at most $s$ times the distance in $G$. We study in this paper spanners that approximate short cycles, and more generally $p$ edge-disjoint paths with $p>1$, between any pair of vertices. For every unweighted graph $G$, we construct a $2$-multipath $3$-spanner of $O(n^3/2)$ edges. In other words, for any two vertices $u,v$ of $G$, the length of the shortest cycle (with no edge replication) traversing $u,v$ in the spanner is at most thrice the length of the shortest one in $G$. This construction is shown to be optimal in term of stretch and of size. In a second construction, we produce a $2$-multipath $(2,8)$-spanner of $O(n^3/2)$ edges, i.e., the length of the shortest cycle traversing any two vertices have length at most twice the shortest length in $G$ plus eight. For arbitrary $p$, we observe that, for each integer $k\ge 1$, every weighted graph has a $p$-multipath $p(2k-1)$-spanner with $O(p n^1+1/k)$ edges, leaving open the question whether, with similar size, the stretch of the spanner can be reduced to $2k-1$ for all $p>1$.
Complete list of metadatas

Cited literature [29 references]  Display  Hide  Download

https://hal.inria.fr/inria-00547869
Contributor : Laurent Viennot <>
Submitted on : Friday, December 17, 2010 - 3:37:58 PM
Last modification on : Thursday, April 4, 2019 - 10:18:04 AM
Long-term archiving on : Monday, November 5, 2012 - 2:35:24 PM

File

sirocco10multipath.pdf
Files produced by the author(s)

Identifiers

Citation

Cyril Gavoille, Quentin Godfroy, Laurent Viennot. Multipath Spanners. Structural Information and Communication Complexity, 17th International Colloquium (SIROCCO), Jun 2010, Sirince, Turkey. pp.211-223, ⟨10.1007/978-3-642-13284-1_17⟩. ⟨inria-00547869⟩

Share

Metrics

Record views

450

Files downloads

206