Nearly Tight Low Stretch Spanning Trees

Simple item page
dc.creatorAbraham, Ittai
dc.creatorBartal, Yair
dc.creatorNeiman, Ofer
dc.date2008-08-14
dc.date.accessioned2026-07-07T09:56:40Z
dc.date.available2026-07-07T09:56:40Z
dc.descriptionWe 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.
dc.identifierhttps://arxiv.org/abs/0808.2017
dc.identifierhttp://arxiv.org/abs/0808.2017
dc.identifier.urihttp://salesiana.dossiersoluciones.com/handle/123456789/167058
dc.subjectData Structures and Algorithms
dc.subjectDiscrete Mathematics
dc.titleNearly Tight Low Stretch Spanning Trees
dc.typetext

Files

Collections

arXiv