2020/04/17 by Glencora Borradaile, Borradaile, Glencora, Erin Wolf Chambers +7
Computer Science · #Data Structures and Algorithms (cs.DS) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #cs.DM #cs.DS
paper · pdf · doi:10.48550/arxiv.2004.08375
arxiv created 2020/04/17 · arxiv updated 2020/04/20
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(b2). 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(b2) with high probability. We also describe a deterministic linear-time algorithm for computing a spanning tree of G with average stretch O(b3). For graphs of cutwidth c, we construct a spanning tree with stretch O(c2) 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.