Nearly Tight Low Stretch Spanning Trees

Abstract

We prove that any graph $G$ with $n$ points has a distribution $\mathcal{T}$ over spanning trees such that for any edge $(u,v)$ the expected stretch $E_{T\sim \mathcal{T}}[d_T(u,v)/d_G(u,v)]$ is bounded by $\tilde{O}(\log n)$. Our result is obtained via a new approach of building ``highways'' between portals and a new strong diameter probabilistic decomposition theorem.

Cited by in corpus (11)

• A nearly-mlogn time solver for SDD linear systems
• Approaching optimality for solving SDD systems
• Fast Approximation Algorithms for Cut-based Problems in Undirected Graphs
• Parallel Graph Decompositions Using Random Shifts
• Computing the log-determinant of symmetric, diagonally dominant matrices in near-linear time
• Faster Subset Selection for Matrices and Applications
• Near-Optimal Distributed Maximum Flow
• Subgraph Sparsification and Nearly Optimal Ultrasparsifiers
• Near Linear-Work Parallel SDD Solvers, Low-Diameter Decomposition, and Low-Stretch Subgraphs
• On Strong Graph Partitions and Universal Steiner Trees
• The Range of Topological Effects on Communication