Average Size of Unstretched Remote-Spanners - Archive ouverte HAL Access content directly
Conference Papers Year : 2009

## Average Size of Unstretched Remote-Spanners

Philippe Jacquet
Laurent Viennot

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

### Dates and versions

inria-00471727 , version 1 (08-04-2010)

### Identifiers

• HAL Id : inria-00471727 , version 1

### Cite

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⟩

### Export

BibTeX TEI Dublin Core DC Terms EndNote Datacite

237 View