License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.MFCS.2019.15
URN: urn:nbn:de:0030-drops-109598
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2019/10959/
Go to the corresponding LIPIcs Volume Portal

Chepoi, Victor ; Labourel, Arnaud ; Ratel, Sébastien

Distance Labeling Schemes for Cube-Free Median Graphs

pdf-format:
LIPIcs-MFCS-2019-15.pdf (0.6 MB)

Abstract

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.

BibTeX - Entry

@InProceedings{chepoi_et_al:LIPIcs:2019:10959,
  author =	{Victor Chepoi and Arnaud Labourel and S{\'e}bastien Ratel},
  title =	{{Distance Labeling Schemes for Cube-Free Median Graphs}},
  booktitle =	{44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019)},
  pages =	{15:1--15:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-117-7},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{138},
  editor =	{Peter Rossmanith and Pinar Heggernes and Joost-Pieter Katoen},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2019/10959},
  URN =		{urn:nbn:de:0030-drops-109598},
  doi =		{10.4230/LIPIcs.MFCS.2019.15},
  annote =	{Keywords: median graphs, labeling schemes, distributed distance computation}
}

Keywords: median graphs, labeling schemes, distributed distance computation
Collection: 44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019)
Issue Date: 2019
Date of publication: 20.08.2019

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI