2026-07-23T14:36:00Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:10959 2024-03-06T10:46:55Z ddc:004 open_access

Distance Labeling Schemes for Cube-Free Median Graphs Chepoi, Victor Labourel, Arnaud Ratel, Sébastien median graphs labeling schemes distributed distance computation 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Victor Chepoi and Arnaud Labourel and Sébastien Ratel 2019 Is Part Of LIPIcs, Volume 138, 44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.MFCS.2019.15 urn:nbn:de:0030-drops-109598 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2019.15 eng https://creativecommons.org/licenses/by/3.0/legalcode