Creative Commons Attribution 3.0 Unported license (CC-BY 3.0)when quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.SWAT.2020.15
URN: urn:nbn:de:0030-drops-122622
URL: https://drops.dagstuhl.de/opus/volltexte/2020/12262/
Borradaile, Glencora ; Chambers, Erin Wolf ; Eppstein, David ; Maxwell, William ; Nayyeri, Amir
Low-Stretch Spanning Trees of Graphs with Bounded Width
| pdf-format: |
|
Abstract
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.
BibTeX - Entry
@InProceedings{borradaile_et_al:LIPIcs:2020:12262,
author = {Glencora Borradaile and Erin Wolf Chambers and David Eppstein and William Maxwell and Amir Nayyeri},
title = {{Low-Stretch Spanning Trees of Graphs with Bounded Width}},
booktitle = {17th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2020)},
pages = {15:1--15:19},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-150-4},
ISSN = {1868-8969},
year = {2020},
volume = {162},
editor = {Susanne Albers},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2020/12262},
URN = {urn:nbn:de:0030-drops-122622},
doi = {10.4230/LIPIcs.SWAT.2020.15},
annote = {Keywords: Treewidth, low-stretch spanning tree, fundamental cycle basis}
}
| Keywords: | Treewidth, low-stretch spanning tree, fundamental cycle basis | |
| Seminar: | 17th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2020) | |
| Issue date: | 2020 | |
| Date of publication: | 12.06.2020 |
