2026-07-25T01:58:08Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:12262 2024-03-06T10:49:28Z ddc:004 open_access

Low-Stretch Spanning Trees of Graphs with Bounded Width Borradaile, Glencora Chambers, Erin Wolf Eppstein, David Maxwell, William Nayyeri, Amir Treewidth low-stretch spanning tree fundamental cycle basis 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Glencora Borradaile and Erin Wolf Chambers and David Eppstein and William Maxwell and Amir Nayyeri 2020 Is Part Of LIPIcs, Volume 162, 17th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2020) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.SWAT.2020.15 urn:nbn:de:0030-drops-122622 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SWAT.2020.15 eng https://creativecommons.org/licenses/by/3.0/legalcode