Subquadratic Dynamic Path Reporting in Directed Graphs Against an Adaptive Adversary

Adam Karczmarz, Anish Mukherjee, Piotr Sankowski

We study reachability and shortest paths problems in dynamic directed graphs. Whereas algebraic dynamic data structures supporting edge updates and reachability/distance queries ha…