A note on distance labeling in planar graphs
A note on distance labeling in planar graphs
复制标题
关于平面图中距离标注的注意事项
DOI：
--
复制
发表时间：
2016
期刊：
影响因子：
--
通讯作者：
P. Uznański
中科院分区：
文献类型：
--
作者：
Paweł Gawrychowski;P. Uznański
距离标记方案是将标签（即二进制字符串）分配给图的所有节点，使得任何两个节点之间的距离可以从它们的标签计算，并且标签尽可能短。一个主要的开放问题是确定距离标记的复杂性在无权和无向平面图。众所周知，在这样一个有n个节点的图中，某些标签必须由$Omega（n^{1/3}）$ bits组成，但最著名的标签方案使用长度为$O（sqrt{n}log n）$的标签[Gavoille，Peleg，P 'erennes，and Raz，J. Algorithms，2004]。我们证明，实际上，长度为$O（sqrt{n}）$的标签就足够了。
A distance labeling scheme is an assignments of labels, that is binary strings, to all nodes of a graph, so that the distance between any two nodes can be computed from their labels and the labels are as short as possible. A major open problem is to determine the complexity of distance labeling in unweighted and undirected planar graphs. It is known that, in such a graph on $n$ nodes, some labels must consist of $Omega(n^{1/3})$ bits, but the best known labeling scheme uses labels of length $O(sqrt{n}log n)$ [Gavoille, Peleg, P'erennes, and Raz, J. Algorithms, 2004]. We show that, in fact, labels of length $O(sqrt{n})$ are enough.