Distance Labeling Schemes for Cube-Free Median Graphs

International audienceDistance labeling schemes are schemes that label the vertices of a graph with short labels in such away that the distance between any two vertices u and v can be determined efficiently by merelyinspecting the labels of u and v, without using any other information. One of the important problemsis finding natural classes of graphs admitting distance labeling schemes with labels of polylogarithmicsize. In this paper, we show that the class of cube-free median graphs on n nodes enjoys distancelabeling scheme with labels of O(log3 n) bits