A Simple Algorithm for the Directed Multiple Source Replacement Paths Problem
A randomized combinatorial algorithm that solves MSRP on unweighted directed graphs in $\tilde{O}(m\sqrt{\sigma n} + \sigma n^2)$ time, with all the output distances correct with high probability.
Kaito Harada, Taisuke Izumi
· 0 citations