Preprint
Sep 2026
Low-Stretch Spanning Trees via Smoothed Analysis of Dijkstra's Algorithm
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 in expectation. Currently, existing algorithms to find a provably good LSST carefully construct an approximate shortest-path tree...
Ioannis Dorkofikis, Bernhard Haeupler, Maximilian Probst Gutenberg et al.
· 0 citations