Detecting Disjoint Shortest Paths in Linear Time and More

Shyan Akmal, Virginia Vassilevska Williams, Nicole Wein

In the $k$-Disjoint Shortest Paths ($k$-DSP) problem, we are given a weighted graph $G$ on $n$ nodes and $m$ edges with specified source vertices $s_1,\dots ,s_k$, and target vert…