First deterministic near-linear time algorithm for negative-weight single-source shortest paths on integer-weighted graphs, via a new deterministic padded decomposition construction on directed graphs.
Maximum flow and minimum-cost flow in almost-linear time
2 Pith papers cite this work. Polarity classification is still indexing.
2
Pith papers citing it
fields
cs.DS 2verdicts
UNVERDICTED 2representative citing papers
A balancing-weights technique lets a randomized augmenting-paths algorithm compute max flow in directed graphs in m + nF time, matching the undirected case.
citing papers explorer
-
Deterministic Padded Decompositions and Negative-Weight Shortest Paths
First deterministic near-linear time algorithm for negative-weight single-source shortest paths on integer-weighted graphs, via a new deterministic padded decomposition construction on directed graphs.
-
Balancing Weights, Directed Sparsification, and Augmenting Paths
A balancing-weights technique lets a randomized augmenting-paths algorithm compute max flow in directed graphs in m + nF time, matching the undirected case.