Distance labeling schemes for K₄-free bridged graphs

2020/07/28 by Victor Chepoi, Chepoi, Victor, Arnaud Labourel +3 · 1 citation
Computer Science · Mathematics · #Advanced Combinatorial Mathematics #Advanced Graph Theory Research #Combinatorics (math.CO) #Complexity and Algorithms in Graphs #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics

paper · doi:10.48550/arxiv.2007.14192

openalex publication_date 2020/07/28 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

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 describe a 4-approximate distance labeling scheme forthe class of K₄-free bridged graphs. This scheme uses labels of poly-logarithmic length O(log n³) allowing a constant decoding time. Given the labels of two vertices u and v, the decoding function returnsa value between the exact distance d_G(u,v) and its quadruple 4d_G(u,v).

Citations

• A note on distance labeling in planar graphs

Cited by

• Boundary rigidity of systolic and Helly complexes

Related

• Sublinear Distance Labeling
• Distance and routing labeling schemes for cube-free median graphs
• Simpler, faster and shorter labels for distances in graphs
• Distance labeling schemes for trees
• A note on distance labeling in planar graphs