Distance and Routing Labeling Schemes for Cube-Free Median Graphs

摘要: Distance labeling schemes are that label the vertices of a graph with short labels in such way distance between any two u and v can be determined efficiently by merely inspecting v, without using other information. Similarly, routing given source node destination node, it is possible to compute port number edge from heads direction destination. One important problems finding natural classes graphs admitting and/or polylogarithmic size. In this paper, we show class cube-free median on n nodes enjoys $$O(\log ^3 n)$$ bits.