Forbidden-Set Distance Labels for Graphs of Bounded Doubling Dimension

This article proposes a forbidden-set labeling scheme for the family of unweighted graphs with doubling dimension bounded by a. For an n-vertex graph G in this family, and for any desired precision parameter epsilon > 0, the labeling scheme stores an O(1 + epsilon(-1))(2 alpha) log(2) n-bit label at each vertex. Given the labels of two end-vertices s and t, and the labels of a set F of "forbidden" vertices and/or edges, our scheme can compute, in O(1 + epsilon(-1))(2 alpha) center dot vertical bar F vertical bar(2) log n time, a 1 + epsilon stretch approximation for the distance between s and t in the graph G \ F. The labeling scheme can be extended into a forbidden-set labeled routing scheme with stretch 1 + epsilon for graphs of bounded doubling dimension.