文章基本信息

标题：Distance Labeling Schemes for Cube-Free Median Graphs
本地全文：下载
作者：Victor Chepoi ; Arnaud Labourel ; Sbastien Ratel 等
期刊名称：LIPIcs : Leibniz International Proceedings in Informatics
电子版ISSN：1868-8969
出版年度：2019
卷号：138
页码：1-14
DOI：10.4230/LIPIcs.MFCS.2019.15
出版社：Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
摘要：Distance labeling schemes are schemes that label the vertices of a graph with short labels in such a way that 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 distance labeling schemes with labels of polylogarithmic size. In this paper, we show that the class of cube-free median graphs on n nodes enjoys distance labeling scheme with labels of O(log^3 n) bits.
关键词：median graphs; labeling schemes; distributed distance computation