4 papers · 1 filter
Reviving Thorup's Shortcut Conjecture
Aaron Bernstein, Henry Fleischmann, Maximilian Probst Gutenberg +7
We aim to revive Thorup's conjecture [Thorup, WG'92] on the existence of reachability shortcuts with ideal size-diameter tradeoffs. Thorup originally asked whether, given any graph…
Separations between Oblivious and Adaptive Adversaries for Natural Dynamic Graph Problems
Aaron Bernstein, Sayan Bhattacharya, Nick Fischer +2
We establish the first update-time separation between dynamic algorithms against oblivious adversaries and those against adaptive adversaries in natural dynamic graph problems, bas…
Combinatorial Maximum Flow via Weighted Push-Relabel on Shortcut Graphs
Aaron Bernstein, Joakim Blikstad, Jason Li +2
We give a combinatorial algorithm for computing exact maximum flows in directed graphs with vertices and edge capacities from in time,…
Deterministic Dynamic Maximal Matching in Sublinear Update Time
Aaron Bernstein, Sayan Bhattacharya, Peter Kiss +1
We give a fully dynamic deterministic algorithm for maintaining a maximal matching of an -vertex graph in amortized update time. This breaks the long-standi…