论文标题
跨越宽度的低伸展图
Low-stretch spanning trees of graphs with bounded width
论文作者
论文摘要
我们研究了有界宽度的图形：带宽，切割和树宽的低伸展树木的问题。我们表明，任何带有带宽$ b $线性布置的简单连接的图形$ g $都可以嵌入到分布树的分配$ \ natercal t $中，以使每种边缘的预期$ g $的预期拉伸为$ o（b^2）$。我们的证明意味着从$ \ Mathcal t $采样的线性时间算法。因此，我们有一种线性时间算法，可以找到一棵$ g $的生成树，平均拉伸$ O（b^2）$具有很高的概率。我们还描述了一种用于计算$ g $的生成树的确定性线性时间算法，其平均拉伸$ o（b^3）$。对于Cutwidth $ C $的图，我们在线性时间内构建了带有strave $ o（c^2）$的生成树。最后，当$ g $具有树宽$ k $时，我们提供了一种动态的编程算法，计算了$ g $的最小伸展树，相对于$ g $的顶点数，在多项式时间内运行。
We study the problem of low-stretch spanning trees in graphs of bounded width: bandwidth, cutwidth, and treewidth. We show that any simple connected graph $G$ with a linear arrangement of bandwidth $b$ can be embedded into a distribution $\mathcal T$ of spanning trees such that the expected stretch of each edge of $G$ is $O(b^2)$. Our proof implies a linear time algorithm for sampling from $\mathcal T$. Therefore, we have a linear time algorithm that finds a spanning tree of $G$ with average stretch $O(b^2)$ with high probability. We also describe a deterministic linear-time algorithm for computing a spanning tree of $G$ with average stretch $O(b^3)$. For graphs of cutwidth $c$, we construct a spanning tree with stretch $O(c^2)$ in linear time. Finally, when $G$ has treewidth $k$ we provide a dynamic programming algorithm computing a minimum stretch spanning tree of $G$ that runs in polynomial time with respect to the number of vertices of $G$.
