Directed Spanners via Flow-Based Linear Programs

Michael Dinitz, Robert Krauthgamer

We examine directed spanners through flow-based linear programming relaxations. We design an $\tilde{O}(n^{2/3})$-approximation algorithm for the directed $k$-spanner problem that works fo…