Low-stretch spanning trees of graphs with bounded width
share
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 𝒯 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 𝒯. 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.
READ FULL TEXT