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$.
Type de document :
Communication dans un congrès
Boaz Patt-Shamir, Tinaz Ekim. Structural Information and Communication Complexity, 17th International Colloquium (SIROCCO), Jun 2010, Sirince, Turkey. Springer, 6058, pp.211-223, 2010, Lecture Notes in Computer Science. 〈http://www.springerlink.com/content/978-3-642-13283-4/〉. 〈10.1007/978-3-642-13284-1_17〉
Liste complète des métadonnées

Littérature citée [29 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/inria-00547869
Contributeur : Laurent Viennot <>
Soumis le : vendredi 17 décembre 2010 - 15:37:58
Dernière modification le : jeudi 11 janvier 2018 - 06:22:11
Document(s) archivé(s) le : lundi 5 novembre 2012 - 14:35:24

Fichier

sirocco10multipath.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

Collections

Citation

Cyril Gavoille, Quentin Godfroy, Laurent Viennot. Multipath Spanners. Boaz Patt-Shamir, Tinaz Ekim. Structural Information and Communication Complexity, 17th International Colloquium (SIROCCO), Jun 2010, Sirince, Turkey. Springer, 6058, pp.211-223, 2010, Lecture Notes in Computer Science. 〈http://www.springerlink.com/content/978-3-642-13283-4/〉. 〈10.1007/978-3-642-13284-1_17〉. 〈inria-00547869〉

Partager

Métriques

Consultations de la notice

347

Téléchargements de fichiers

115