Low-Stretch Spanning Trees via Smoothed Analysis of Dijkstra's Algorithm

Ioannis Dorkofikis, Bernhard Haeupler, Maximilian Probst Gutenberg +3

Given an undirected weighted graph $G$, a $\gamma$-approximate low-stretch spanning tree (LSST) $T\subseteq G$ is a tree that approximates the distance metric of $G$ up to a $\gamma$-factor…