Average Size of Unstretched Remote-Spanners

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, Polytechnique - X, 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 optimization of link state routing in ad hoc networks, and the concept of multipoint relays, we introduce the notion of remote-spanner. Given an unweighted graph $G$, a remote spanner is a set of links $H$ such that for any pair of nodes $(u,v)$ there exists a shortest path in $G$ for which all links in the path that are not adjacent to $u$ belong to $H$. The remote spanner is a kind of minimal topology information beyond its neighborhood that any node would need in order to compute its shortest paths in a distributed way. This can be extended to $k$-connected graphs by considering minimum length sum over $k$ disjoint paths as distance. In this paper, we give distributed algorithms for computing remote-spanners in order to obtain sparse remote-spanners with various properties. We provide a polynomial distributed algorithm that computes a $k$-connecting unstretched remote-spanner whose number of edges is at a factor $2(1+\log \Delta)$ from optimal where $\Delta$ is the maximum degree of a node. Interestingly, its expected compression ratio in number of edges is $O(\frackn\log n)$ in Erdös-Rényi graph model and $O((\frackn)^\frac23)$ in the unit disk graph model with a uniform Poisson distribution of nodes.
Type de document :
Communication dans un congrès
5th ACM Workshop on Analytic Algorithmics and Combinatorics (ANALCO), 2009, New York, United States. SIAM, pp.23--33, 2009, 〈http://www.siam.org/proceedings/analco/2009/anl09_004_jacquetp.pdf〉
Liste complète des métadonnées

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

https://hal.inria.fr/inria-00471727
Contributeur : Laurent Viennot <>
Soumis le : jeudi 8 avril 2010 - 17:53:14
Dernière modification le : jeudi 11 janvier 2018 - 06:22:23
Document(s) archivé(s) le : mardi 14 septembre 2010 - 18:09:30

Fichier

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

Identifiants

  • HAL Id : inria-00471727, version 1

Collections

Citation

Philippe Jacquet, Laurent Viennot. Average Size of Unstretched Remote-Spanners. 5th ACM Workshop on Analytic Algorithmics and Combinatorics (ANALCO), 2009, New York, United States. SIAM, pp.23--33, 2009, 〈http://www.siam.org/proceedings/analco/2009/anl09_004_jacquetp.pdf〉. 〈inria-00471727〉

Partager

Métriques

Consultations de la notice

391

Téléchargements de fichiers

189