文章基本信息

标题：Low-Stretch Spanning Trees of Graphs with Bounded Width
本地全文：下载
作者：Glencora Borradaile ; Erin Wolf Chambers ; David Eppstein 等
期刊名称：LIPIcs : Leibniz International Proceedings in Informatics
电子版ISSN：1868-8969
出版年度：2020
卷号：162
页码：15:1-15:19
DOI：10.4230/LIPIcs.SWAT.2020.15
出版社：Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
摘要：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 T of spanning trees such that the expected stretch of each edge of G is O(bÂ²). Our proof implies a linear time algorithm for sampling from T. Therefore, we have a linear time algorithm that finds a spanning tree of G with average stretch O(bÂ²) with high probability. We also describe a deterministic linear-time algorithm for computing a spanning tree of G with average stretch O(bÂ³). For graphs of cutwidth c, we construct a spanning tree with stretch O(cÂ²) 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.
关键词：Treewidth; low-stretch spanning tree; fundamental cycle basis