Finding single-source shortest $p$-disjoint paths: fast computation and sparse preservers

Davide Bilò, Gianlorenzo D'Angelo, Luciano Gualà +3

Let $G$ be a directed graph with $n$ vertices, $m$ edges, and non-negative edge costs. Given $G$, a fixed source vertex $s$, and a positive integer $p$, we consider the problem of…