Exact Minimum Weight Spanners via Column Generation

Fritz Bökler, Markus Chimani, Henning Jasper +1

Given a weighted graph $G$, a minimum weight $\alpha$-spanner is a least-weight subgraph $H\subseteq G$ that preserves minimum distances between all node pairs up to a factor of $\alpha$. Th…