论文标题
较短的标签用于在树上布线
Shorter Labels for Routing in Trees
论文作者
论文摘要
一个路由标签方案将一个名为“标签”的二进制字符串分配给网络中的每个节点，并选择一个不同的端口号从$ \ {1，\ ldots，d \} $中的每个边缘从度数$ d $的节点中传出。然后，鉴于$ u $和$ w $的标签，并且没有有关网络的其他信息，应该可以确定与第一个边缘相对应的端口号，从$ u $到$ w $。 Thorup和Zwick [Spaa 2001]在他们的开创性论文中设计了多种针对一般加权网络的路由方法。根据作者``可能具有独立实用且理论上的利益''的重要技术成分，它是针对任意学位树木的路由标签方案。对于$ n $节点上的树，他们的方案构造标签由$（1+o（1））\ log n $位组成，以便可以在恒定时间内计算所寻求的端口号。仔细观察其构造，标签由$ \ log n + o（\ log n \ cdot \ log \ log \ log \ log \ log \ log n / \ log \ log \ log n）$ bits。鉴于唯一已知的下限是$ \ log n+ω（\ log \ log n）$，这是一个自然的问题，被要求在树中出现其他标记问题是确定较小级术语的渐近性。 我们在19年内取得了第一个（且重大）的进展，以确定在$ n $ nodes上的树木路由标签方案中标签长度的正确二阶期限。我们设计了这样的方案，该方案的长度为$ \ log n+o（（（\ log \ log \ log n）^{2}）$。此外，我们修改了该方案，以允许在恒定时间内计算端口号，而费用将长度稍微增加到$ \ log n+o（（（（\ log \ log \ log \ log \ log n）^{3}）$。
A routing labeling scheme assigns a binary string, called a label, to each node in a network, and chooses a distinct port number from $\{1,\ldots,d\}$ for every edge outgoing from a node of degree $d$. Then, given the labels of $u$ and $w$ and no other information about the network, it should be possible to determine the port number corresponding to the first edge on the shortest path from $u$ to $w$. In their seminal paper, Thorup and Zwick [SPAA 2001] designed several routing methods for general weighted networks. An important technical ingredient in their paper that according to the authors ``may be of independent practical and theoretical interest'' is a routing labeling scheme for trees of arbitrary degrees. For a tree on $n$ nodes, their scheme constructs labels consisting of $(1+o(1))\log n$ bits such that the sought port number can be computed in constant time. Looking closer at their construction, the labels consist of $\log n + O(\log n\cdot \log\log\log n / \log\log n)$ bits. Given that the only known lower bound is $\log n+Ω(\log\log n)$, a natural question that has been asked for other labeling problems in trees is to determine the asymptotics of the smaller-order term. We make the first (and significant) progress in 19 years on determining the correct second-order term for the length of a label in a routing labeling scheme for trees on $n$ nodes. We design such a scheme with labels of length $\log n+O((\log\log n)^{2})$. Furthermore, we modify the scheme to allow for computing the port number in constant time at the expense of slightly increasing the length to $\log n+O((\log\log n)^{3})$.
