NAVIGATING IN A GRAPH BY AID OF ITS SPANNING TREE METRIC

Let G - (V, E) be a graph and T be a spanning tree of G. We consider the following strategy in advancing in G from a vertex x towards a target vertex y: from a current vertex z (initially, z = x), unless z = y, go to a neighbor of z in G that is closest to y in T (breaking ties arbitrarily). In this strategy, each vertex has full knowledge of its neighborhood in G and can use the distances in T to navigate in G. Thus, additionally to standard local information (the neighborhood N-G(upsilon)), the only global information that is available to each vertex upsilon is the topology of the spanning tree T (in fact, upsilon can know only a very small piece of information about T and still be able to infer from it the necessary tree-distances). For each source vertex x and target vertex y, this way, a path, called a greedy routing path, is produced. Denote by g(G,T) (x, y) the length of a longest greedy routing path that can be produced for x and y using this strategy and T. We say that a spanning tree T of a graph G is an additive r-carcass for G if g(G,T) (x, y) <= d(G)(x, y) + r for each ordered pair x, y epsilon V. In this paper, we investigate the problem, given a graph family F, of whether a small integer r exists such that any graph G epsilon F admits an additive r-carcass. We show that rectilinear p x q grids, hypercubes, distance-hereditary graphs, dually chordal graphs (and, therefore, strongly chordal graphs and interval graphs) all admit additive 0-carcasses. Furthermore, every chordal graph G admits an additive (omega + 1)-carcass (where omega is the size of a maximum clique of G), each 3-sun-free chordal graph admits an additive 2-carcass, and each chordal bipartite graph admits an additive 4-carcass. In particular, any k-tree admits an additive (k + 2)-carcass. All those carcasses are easy to construct in sequential as well as in distributed settings.