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, 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 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.
Complete list of metadatas

Cited literature [34 references]  Display  Hide  Download

https://hal.inria.fr/inria-00471727
Contributor : Laurent Viennot <>
Submitted on : Thursday, April 8, 2010 - 5:53:14 PM
Last modification on : Thursday, February 7, 2019 - 4:33:40 PM
Long-term archiving on : Tuesday, September 14, 2010 - 6:09:30 PM

File

analco2009remote.pdf
Files produced by the author(s)

Identifiers

  • 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. pp.23--33. ⟨inria-00471727⟩

Share

Metrics

Record views

463

Files downloads

244