论文标题
树公制1-Spanner中的本地路由
Local Routing in a Tree Metric 1-Spanner
论文作者
论文摘要
所罗门和埃尔金（Elkin）为加权树构建了捷径方案，为输入树引起的树度量导致1跨度。扳手具有对数轻度，对数直径，线性的边缘和有界度（前提是输入树具有界限）。该扳手已在一系列论文中应用，用于设计有限的程度，低直径，低重量$（1+ε）$ - 欧几里得和双倍指标。在本文中，我们为该树度跨度提供了一种简单的本地路由算法。该算法的路由比为1，保证在$ O（\ log n）$ hops之后终止，并且需要$ o（δ\ log n）$存储，其中$δ$是构建跨度的树的最大程度。该本地路由算法可以适应使用捷径方案的双倍跨度的本地路由算法。
Solomon and Elkin constructed a shortcutting scheme for weighted trees which results in a 1-spanner for the tree metric induced by the input tree. The spanner has logarithmic lightness, logarithmic diameter, a linear number of edges and bounded degree (provided the input tree has bounded degree). This spanner has been applied in a series of papers devoted to designing bounded degree, low-diameter, low-weight $(1+ε)$-spanners in Euclidean and doubling metrics. In this paper, we present a simple local routing algorithm for this tree metric spanner. The algorithm has a routing ratio of 1, is guaranteed to terminate after $O(\log n)$ hops and requires $O(Δ\log n)$ bits of storage per vertex where $Δ$ is the maximum degree of the tree on which the spanner is constructed. This local routing algorithm can be adapted to a local routing algorithm for a doubling metric spanner which makes use of the shortcutting scheme.
