k-Approximate distance labeling schemes are schemes that label the vertices of a graph with short labels in such a way that the k-approximation of the distance between any two vertices u and v can be determined efficiently by merely inspecting the labels of u and v, without using any other information. One of the important problems is finding natural classes of graphs admitting exact or approximate distance labeling schemes with labels of polylogarithmic size. In this paper, we show that the class of K_4-free bridged graphs on n nodes enjoys 4-approximate distance labeling scheme with labels of O(log~3 n) bits.
展开▼
