论文标题
$ k_4 $ - 免费的桥接图的距离标签方案
Distance labeling schemes for $K_4$-free bridged graphs
论文作者
论文摘要
$ k $ - 适当的距离标签方案是图案，其标记图形标签的顶点具有短标签，以使$ k $ - 可以通过仅使用任何其他信息而无需检查$ u $和$ v $的标签，从而有效地确定任意两个顶点$ u $和$ v $之间的任何两个顶点$ u $和$ v $之间距离的距离。重要的问题之一是找到自然的图形类别，即具有具有多层次大小的标签的精确或近似距离标记方案。在本文中，我们描述了$ k_4 $ fre-Fre-Fre-Fre-Fre-Bridged Graphs的$ 4 $ approximate距离标签方案。该方案使用poly-logarithmic长度$ o（\ log n^3）$的标签，允许恒定的解码时间。给定两个顶点$ u $和$ v $的标签，解码函数返回确切距离$ d_g（u，v）$和其Quadruple $ 4D_G（u，v）$之间的值。
$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_4$-free bridged graphs. This scheme uses labels of poly-logarithmic length $O(\log n^3)$ 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)$.
