Deterministic Padded Decompositions and Negative-Weight Shortest Paths
Abstract
We obtain the first near-linear time deterministic algorithm for negative-weight single-source shortest paths on integer-weighted graphs. Our main ingredient is a deterministic construction of a padded decomposition on directed graphs, which may be of independent interest.
Fields of Study & Subjects
Complexity and Algorithms in Graphs
Markov Chains and Monte Carlo Methods
Sparse and Compressive Sensing Techniques
Publication details
- Pages
- 13–18
- Publication date
- 9 June 2026