Remote-spanners: What to know beyond neighbors

摘要

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 (alpha, beta)-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 alpha times the distance between u and v in G plus beta. 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 (alpha, beta)-remote-spanner is k-connecting. In this paper, we give distributed algorithms for computing (1 + epsiv, 1 - 2epsiv)-remote-spanners for any epsiv > 0, k-connecting (1, 0)-remote-spanners for any k ges 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 + epsiv, 1-2epsiv)-remote-spanners 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.