2 papers
cs.DS2026
A Near-Optimal Offline Algorithm for Dynamic All-Pairs Shortest Paths in Planar Digraphs
Debarati Das, Maximilian Probst Gutenberg, Christian Wulff-Nilsen
In the planar, dynamic All-Pairs Shortest Paths (APSP) problem, a planar, weighted digraph undergoes a sequence of edge weight updates and the goal is to maintain a data struct…
cs.DS2025
Negative-Weight Single-Source Shortest Paths in Near-linear Time
Aaron Bernstein, Danupon Nanongkai, Christian Wulff-Nilsen
We present a randomized algorithm that computes single-source shortest paths (SSSP) in time when edge weights are integral and can be negative. This essential…