Document Open Access Logo

Distance Labeling Schemes for Cube-Free Median Graphs

Authors Victor Chepoi, Arnaud Labourel, Sébastien Ratel

PDF

File

Thumbnail PDF
PDF
LIPIcs.MFCS.2019.15.pdf
  • Filesize: 0.57 MB
  • 14 pages

Document Identifiers

Related Versions

Subject Classification

ACM Subject Classification
  • Mathematics of computing → Graph algorithms
Keywords
  • median graphs
  • labeling schemes
  • distributed distance computation

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

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.

Cite As Get BibTex

Victor Chepoi, Arnaud Labourel, and Sébastien Ratel. Distance Labeling Schemes for Cube-Free Median Graphs. In 44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 138, pp. 15:1-15:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019) https://doi.org/10.4230/LIPIcs.MFCS.2019.15

Author Details

Victor Chepoi
  • Aix Marseille Université, Université de Toulon, CNRS, LIS, Marseille, France
Arnaud Labourel
  • Aix Marseille Université, Université de Toulon, CNRS, LIS, Marseille, France
Sébastien Ratel
  • Aix Marseille Université, Université de Toulon, CNRS, LIS, Marseille, France

Funding

The work on this paper was supported by ANR project DISTANCIA (ANR-17-CE40-0015).

References

  1. A. Abrams and R. Ghrist. State complexes for metamorphic robots. Intl. J. Robotics Res., 23(7-8):811-826, 2004. URL: https://doi.org/10.1177/0278364904045468.
  2. S. Alstrup, C. Gavoille, E.B. Halvorsen, and H. Petersen. Simpler, faster and shorter labels for distances in graphs. In SODA, pages 338-350, 2016. Google Scholar
  3. S. Alstrup, I.L. Gørtz, E.B. Halvorsen, and E. Porat. Distance Labeling Schemes for Trees. In ICALP, pages 132:1-132:16, 2016. Google Scholar
  4. H.-J. Bandelt. Retracts of hypercubes. J. Graph Theory, 8(4):501-510, 1984. URL: https://doi.org/10.1002/jgt.3190080407.
  5. H.-J. Bandelt and V. Chepoi. Metric graph theory and geometry: a survey. Contemporary Mathematics, 453:49-86, 2008. Google Scholar
  6. H.-J. Bandelt, V. Chepoi, and D. Eppstein. Ramified rectilinear polygons: coordinatization by dendrons. Discr. Comput. Geom., 54(4):771-797, 2015. URL: https://doi.org/10.1007/s00454-015-9743-5.
  7. H.-J. Bandelt and J. Hedlíková. Median algebras. Discr. Math., 45(1):1-30, 1983. Google Scholar
  8. H.-J. Bandelt and M. van de Vel. Embedding topological median algebras in products of dendrons. Proc. London Math. Soc., s3-58(3):439-453, 1989. Google Scholar
  9. F. Bazzaro and C. Gavoille. Localized and compact data-structure for comparability graphs. Discr. Math., 309(11):3465-3484, 2009. Google Scholar
  10. L. J. Billera, S.P. Holmes, and K. Vogtmann. Geometry of the space of phylogenetic trees. Adv. Appl. Math., 27:733-767, 2001. Google Scholar
  11. B. Brešar, S. Klavžar, and R. Škrekovski. On cube-free median graphs. Discr. Math., 307(3-5):345-351, 2007. Google Scholar
  12. M. A. Breuer and J. Folkman. An unexpected result in coding the vertices of a graph. J. Math. Anal. Appl., 20(3):583-600, 1967. Google Scholar
  13. M.R. Bridson and A. Haefliger. Metric Spaces of Non-Positive Curvature, volume 319 of Grundlehren der mathematischen Wissenschaften. Springer-Verlag, Berlin, 1999. Google Scholar
  14. J. Chalopin and V. Chepoi. A Counterexample to Thiagarajan’s Conjecture on Regular Event Structures. In ICALP, pages 101:1-101:14. arXiv:1605.08288, 2017. Google Scholar
  15. J. Chalopin, V. Chepoi, H. Hirai, and D. Osajda. Weakly modular graphs and nonpositive curvature. Memoirs of AMS, (to appear). Google Scholar
  16. M. Chastand. Fiber-complemented graphs. I. Structure and invariant subgraphs. Discr. Math., 226(1-3):107-141, 2001. Google Scholar
  17. V. Chepoi. Classification of graphs by means of metric triangles. Metody Diskret. Analiz., 49:75-93, 96, 1989. Google Scholar
  18. V. Chepoi. Graphs of some CAT(0) complexes. Adv. Appl. Math., 24(2):125-179, 2000. Google Scholar
  19. V. Chepoi, F. F. Dragan, and Y. Vaxès. Distance and routing labeling schemes for non-positively curved plane graphs. J. Algorithms, 61(2):60-88, 2006. Google Scholar
  20. V. Chepoi and M. F. Hagen. On embeddings of CAT(0) cube complexes into products of trees via colouring their hyperplanes. J. Comb. Theory, Ser. B, 103(4):428-467, 2013. Google Scholar
  21. V. Chepoi, A. Labourel, and S. Ratel. On density of subgraphs of Cartesian products. CoRR, abs/1711.11485, 2017. URL: http://arxiv.org/abs/1711.11485.
  22. Victor Chepoi, Arnaud Labourel, and Sébastien Ratel. Distance and routing labeling schemes for cube-free median graphs. CoRR, abs/1809.10508, 2018. URL: http://arxiv.org/abs/1809.10508.
  23. B. Courcelle and R. Vanicat. Query efficient implementation of graphs of bounded clique-width. Discr. Appl. Math., 131(1):129-150, 2003. Google Scholar
  24. O. Freedman, P. Gawrychowski, P. K. Nicholson, and O. Weimann. Optimal distance labeling schemes for trees. In Proceedings of the ACM Symposium on Principles of Distributed Computing, pages 185-194. ACM, 2017. Google Scholar
  25. C. Gavoille and C. Paul. Distance labeling scheme and split decomposition. Discr. Math., 273(1-3):115-130, 2003. Google Scholar
  26. C. Gavoille and C. Paul. Optimal distance labeling for interval graphs and related graph families. SIAM J. Discr. Math., 22(3):1239-1258, 2008. Google Scholar
  27. C. Gavoille, D. Peleg, S. Pérennes, and R. Raz. Distance labeling in graphs. J. Algorithms, 53(1):85-112, 2004. Google Scholar
  28. P. Gawrychowski and P. Uznanski. A note on distance labeling in planar graphs. CoRR, abs/1611.06529, 2016. URL: http://arxiv.org/abs/1611.06529.
  29. R. Ghirst and Peterson V. The geometry and topology of reconfiguration. Adv. Appl. Math., 38:302-323, 2007. Google Scholar
  30. M. Gromov. Hyperbolic groups. In S. M. Gersten, editor, Essays in group theory, volume 8 of Math. Sci. Res. Inst. Publ., pages 75-263. Springer, New York, 1987. Google Scholar
  31. K. Hayashi. A Polynomial Time Algorithm to Compute Geodesics in CAT(0) Cubical Complexes. In ICALP, pages 78:1-78:14, 2018. Google Scholar
  32. S. Kannan, M. Naor, and S. Rudich. Implicit representation of graphs. SIAM J. Discr. Math., 5(4):596-603, 1992. Google Scholar
  33. S. Klavžar and H.M. Mulder. Median Graphs: characterizations, Location Theory and Related Structures. J. Combin. Math. Combin. Comput., 30:103-127, 1999. Google Scholar
  34. D.E. Knuth. The Art of Computer Programming : Vol. 4. Fascicle 0, Introduction to combinatorial algorithms and Boolean functions. Boston, Mass. ; London : Addison-Wesley, 2008. "Newly available sections of the classic work" -cover. Google Scholar
  35. H.M. Mulder. The Interval Function of a Graph, volume 132 of Mathematical Centre Tracts. Mathematisch Centrum, Amsterdam, 1980. Google Scholar
  36. H.M. Mulder and A. Schrijver. Median graphs and Helly hypergraphs. Discr. Math., 25(1):41-50, 1979. URL: https://doi.org/10.1016/0012-365X(79)90151-1.
  37. M. Owen and J.S. Provan. A Fast Algorithm for Computing Geodesic Distances in Tree Space. IEEE/ACM Trans. Comput. Biol. Bioinform., 8(1):2-13, 2011. URL: https://doi.org/10.1109/TCBB.2010.3.
  38. D. Peleg. Proximity-preserving labeling schemes. J. Graph Theory, 33(3):167-176, 2000. URL: https://doi.org/10.1002/(SICI)1097-0118(200003)33:3%3C167::AID-JGT7%3E3.0.CO;2-5.
  39. D. Peleg. Informative labeling schemes for graphs. Theor. Comput. Sci., 340(3):577-593, 2005. Google Scholar
  40. M. Roller. Poc sets, median algebras and group actions. Technical report, Univ. of Southampton, 1998. Google Scholar
  41. M. Sageev. CAT(0) cube complexes and groups. In M. Bestvina, M. Sageev, and K. Vogtmann, editors, Geometric Group Theory, volume 21 of IAS/Park City Mathematics Series, pages 6-53. AMS, Institute for Advanced Study, 2012. Google Scholar
  42. T.J. Schaefer. The complexity of satisfiability problems. In STOC, pages 216-226, 1978. URL: https://doi.org/10.1145/800133.804350.
  43. P. M. Winkler. Proof of the squashed cube conjecture. Combinatorica, 3(1):135-139, 1983. Google Scholar
  44. G. Winskel and M. Nielsen. Models for Concurrency. In S. Abramsky, Dov M. Gabbay, and T. S. E. Maibaum, editors, Handbook of Logic in Computer Science (Vol. 4), pages 1-148. Oxford University Press, 1995. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2025 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact