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 V (H) = V (G) is an (α, β)-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 α times the distance between u and v in G plus β. We extend this definition to k-connected graphs by considering the minimum length sum over k disjoint paths as a distance. We then say that an (α, β)-remote-spanner is k-connecting. In this paper, we give distributed algorithms for computing (1 + ε, 1 − 2ε)-remote-spanners for any ε > 0, k-connecting (1, 0)-remote-spanners for any k ≥ 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 O(n 4/3 ) edges exist in random unit disk graphs. The number of edges obtained for (1+ε, 1−2ε)-remotespanners and 2-connecting (2, −1)-remote-spanners is linear if the input graph is the unit ball graph of a doubling metric (even if 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.
Distributed algorithms for computing k-connecting (1, 0)-remote-spanners with optimal number of edges up to a logarithmic factor are also proposed in REF .
Remote-spanners: What to know beyond neighbors
2009 IEEE International Symposium on Parallel & Distributed Processing
2009 IEEE International Symposium on Parallel & Distributed Processing
Computer Science