Low-stretch spanning trees of graphs with bounded width.
G. Borradaile,
E. Chambers,
D. Eppstein,
W. Maxwell, and
A. Nayyeri.
arXiv:2004.08375.
Proc. 17th Scandinavian Symposium and Workshops on Algorithm
Theory (SWAT 2020).
Leibniz International
Proceedings in Informatics (LIPIcs) 162, 2020, pp. 15:1–15:19, doi:10.4230/LIPIcs.SWAT.2020.15.
We describe a random distribution on the spanning trees of bounded-bandwidth graphs such that each edge has bounded expected stretch, along with several related results for other kinds of graph widths.
(Blog post: Stretch, average stretch, and expected stretch of spanning trees)