Remote spanners: what to know beyond neighbors

Philippe Jacquet 1 Laurent Viennot 2
1 HIPERCOM - High performance communication
Inria Paris-Rocquencourt, UP11 - Université Paris-Sud - Paris 11, Inria Saclay - Ile de France, X - École polytechnique, CNRS - Centre National de la Recherche Scientifique : UMR
2 GANG - Networks, Graphs and Algorithms
LIAFA - Laboratoire d'informatique Algorithmique : Fondements et Applications, Inria Paris-Rocquencourt
Abstract : Motivated by the fact that neighbors are generally known in practical routing algorithms, we introduce the notion of remote-spanner. Given an unweighted graph $G$, a sub-graph $H$ with vertex set $V(H)=V(G)$ is an \emph{$(\a,\b)$-remote-spanner} if for each pair of points $u$ and $v$ the distance between $u$ and $v$ in $H_u$, the graph $H$ augmented by all the edges between $u$ and its neighbors in $G$, is at most $\a$ times the distance between $u$ and $v$ in $G$ plus $\b$. We extend this definition to $k$-connected graphs by considering minimum length sum over $k$ disjoint paths as distance. We then say that an $(\a,\b)$-remote-spanner is \emph{$k$-connecting }. In this paper, we give distributed algorithms for computing $(1+\eps,1-2\eps)$-remote-spanners for any $\eps>0$, $k$-connecting $(1,0)$-remote-spanners for any $k\ge 1$ (yielding $(1,0)$-remote-spanners for $k=1$) and $2$-connecting $(2,-1)$-remote-spanners. All these algorithms run in constant time for any unweighted input graph. The number of edges obtained for $k$-connecting $(1,0)$-remote-spanner is within a logarithmic factor from optimal (compared to the best $k$-connecting $(1,0)$-remote-spanner of the input graph). Interestingly, sparse $(1,0)$-remote-spanners (i.e. preserving exact distances) with $O(n^4/3)$ edges exist in random unit disk graphs. The number of edges obtained for $(1+\eps,1-2\eps)$-remote-spanners and $2$-connecting $(2,-1)$-remote-spanners is linear if the input graph is the unit ball graph of a doubling metric (distances between nodes are unknown). Our methodology consists in characterizing remote-spanners as sub-graphs containing the union of small depth tree sub-graphs dominating nearby nodes. This leads to simple local distributed algorithms.
Type de document :
Communication dans un congrès
23rd IEEE International Parallel and Distributed Processing Symposium (IPDPS), May 2009, Rome, Italy. IEEE, pp.1--10, 2009, 〈10.1109/IPDPS.2009.5161041〉
Liste complète des métadonnées

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

https://hal.inria.fr/inria-00471726
Contributeur : Laurent Viennot <>
Soumis le : jeudi 8 avril 2010 - 17:53:13
Dernière modification le : vendredi 25 mai 2018 - 12:02:06
Document(s) archivé(s) le : vendredi 19 octobre 2012 - 11:26:47

Fichier

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

Identifiants

Collections

Citation

Philippe Jacquet, Laurent Viennot. Remote spanners: what to know beyond neighbors. 23rd IEEE International Parallel and Distributed Processing Symposium (IPDPS), May 2009, Rome, Italy. IEEE, pp.1--10, 2009, 〈10.1109/IPDPS.2009.5161041〉. 〈inria-00471726〉

Partager

Métriques

Consultations de la notice

238

Téléchargements de fichiers

160