# Average Size of Unstretched Remote-Spanners

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.
Document type :
Conference papers
Domain :

Cited literature [34 references]

https://hal.inria.fr/inria-00471727
Contributor : Laurent Viennot <>
Submitted on : Thursday, April 8, 2010 - 5:53:14 PM
Last modification on : Wednesday, September 16, 2020 - 5:06:41 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

### 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⟩

Record views