Abstract
k-Approximate distance labeling schemes are schemes that label the vertices of a graph with short labels in such a way that the k-approximation of 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 exact or approximate distance labeling schemes with labels of polylogarithmic size. In this paper, we show that the class of \(K_4\)-free bridged graphs on n nodes enjoys 4-approximate distance labeling scheme with labels of \(O(\log ^3 n)\) bits.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
References
Bandelt, H.J., Chepoi, V.: A Helly theorem in weakly modular space. Discret. Math. 160(1–3), 25–39 (1996)
Bandelt, H.J., Chepoi, V.: The algebra of metric betweenness ii: axiomatics of weakly median graphs. Euro. J. Combin. 29, 676–700 (2008)
Bandelt, H.J., Chepoi, V.: Metric graph theory and geometry: a survey. Contemp. Math. 453, 49–86 (2008)
Bazzaro, F., Gavoille, C.: Localized and compact data-structure for comparability graphs. Discret. Math. 309, 3465–3484 (2009)
Chalopin, J., Chepoi, V., Hirai, H., Osajda, D.: Weakly modular graphs and nonpositive curvature. Memoirs of AMS (2019)
Chepoi, V.: Graphs of some CAT(0) complexes. Adv. Appl. Math. 24, 125–179 (2000)
Chepoi, V.: Classification of graphs by means of metric triangles. Metody Diskret. Analiz. 45, 75–93 (1989)
Chepoi, V., Dragan, F.F., Vaxès, Y.: Distance and routing labeling schemes for non-positively curved plane graphs. J. Algorithms 61, 60–88 (2006)
Chepoi, V., Labourel, A., Ratel, S.: Distance labeling schemes for cube-free median graphs. In: MFCS. vol. 138, pp. 15:1–15:14 (2019)
Courcelle, B., Vanicat, R.: Query efficient implementation of graphs of bounded clique-width. Discret. Appl. Math. 131, 129–150 (2003)
Farber, M., Jamison, R.E.: On local convexity in graphs. Discret. Math. 66(3), 231–247 (1987)
Freedman, O., Gawrychowski, P., Nicholson, P.K., Weimann, O.: Optimal distance labeling schemes for trees. In: PODC, pp. 185–194. ACM (2017)
Gavoille, C., Katz, M., Katz, N.A., Paul, C., Peleg, D.: Approximate distance labeling schemes. In: auf der Heide, F.M. (ed.) ESA 2001. LNCS, vol. 2161, pp. 476–487. Springer, Heidelberg (2001). https://doi.org/10.1007/3-540-44676-1_40
Gavoille, C., Paul, C.: Distance labeling scheme and split decomposition. Discret. Math. 273, 115–130 (2003)
Gavoille, C., Paul, C.: Optimal distance labeling for interval graphs and related graph families. SIAM J. Discret. Math. 22, 1239–1258 (2008)
Gavoille, C., Peleg, D., Pérennès, S., Raz, R.: Distance labeling in graphs. J. Algorithms 53, 85–112 (2004)
Gawrychowski, P., Uznanski, P.: A note on distance labeling in planar graphs. CoRR abs/1611.06529 (2016). http://arxiv.org/abs/1611.06529
Januszkiewicz, T., Świa̧tkowski, J.: Simplicial nonpositive curvature. Publications Mathématiques de l’Institut des Hautes Études Scientifiques, 104(1), 1–85 (2006). https://doi.org/10.1007/s10240-006-0038-5
Peleg, D.: Distributed Computing: A Locality-Sensitive Approach. SIAM, Philadelphia (2000)
Ratel, S.: Densité. Aix-Marseille Université, VC-dimension et étiquetages de graphes (2019)
Soltan, V.P., Chepoi, V.: Conditions for invariance of set diameters under \(d\)-convexification in a graph. Cybernetics 19(6), 750–756 (1983). https://doi.org/10.1007/BF01068561
Thorup, M.: Compact oracles for reachability and approximate distances in planar digraphs. J. ACM 51, 993–1024 (2004)
Acknowledgment
The work on this paper was supported by ANR project DISTANCIA (ANR-17-CE40-0015).
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2020 Springer Nature Switzerland AG
About this paper
Cite this paper
Chepoi, V., Labourel, A., Ratel, S. (2020). Distance Labeling Schemes for \(K_4\)-Free Bridged Graphs. In: Richa, A., Scheideler, C. (eds) Structural Information and Communication Complexity. SIROCCO 2020. Lecture Notes in Computer Science(), vol 12156. Springer, Cham. https://doi.org/10.1007/978-3-030-54921-3_18
Download citation
DOI: https://doi.org/10.1007/978-3-030-54921-3_18
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-030-54920-6
Online ISBN: 978-3-030-54921-3
eBook Packages: Computer ScienceComputer Science (R0)