Remote-Spanners: What to Know beyond NeighborsReport as inadecuate

Remote-Spanners: What to Know beyond Neighbors - Download this document for free, or read online. Document in PDF available to download.

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 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 $VH=VG$ 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 $On^{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.

Keywords : spanner k-connected

Author: Philippe Jacquet - Laurent Viennot -



Related documents