Faster shortest-path algorithms using the acyclic-connected tree

Elis Stefansson, Oliver Biggar, Karl H. Johansson

We provide a method to obtain beyond-worst-case time complexity for any single-source-shortest-path (SSSP) algorithm by exploiting modular structures in graphs. The key novelty is…