A deterministic almost-linear time algorithm for minimum-cost flow

DOI10.1109/FOCS57990.2023.00037MaRDI QIDQ6942935zbMATH OpenFDO

Authors Jan van Den Brand, Li Chen, Rasmus Kyng, Yang P. Liu, Richard Peng, Maximilian Probst Gutenberg, Sushant Sachdeva, Aaron Sidford

Publication date 15 August 2025

Full work available at URL https://doi.org/10.1109/FOCS57990.2023.00037

Mathematics Subject Classification ID

Directed graphs (digraphs), tournaments (05C20) Flows in graphs (05C21) Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Programming involving graphs or networks (90C35)

Cited in

(25)

• Color-constrained arborescences in edge-colored digraphs
• The parameterized complexity landscape of two-sets cut-uncut
• A simple and fast algorithm for fair cuts
• Approximation algorithm for extracting densest subgraph over matching-like constraints
• Parameterized algorithms for the spanning forest isomorphism and containment on tree
• Packing dimers to maximum occupancy under soft-core constraints
• Arborescences and shortest path trees when colors matter
• Deterministic minimum cut in poly-logarithmic maximum flows
• Vertex connectivity in poly-logarithmic max-flows
• Maximum flow and minimum-cost flow in almost-linear time
• Combinatorial optimization. Abstracts from the workshop held November 10--15, 2024
• A near-linear time algorithm and a min-cost flow approach for determining the optimal landing times of a fixed sequence of planes
• Deterministic minimum Steiner cut in maximum flow time
• A simple deterministic near-linear time approximation scheme for transshipment with arbitrary positive edge costs
• Practical expander decomposition
• The algorithmic power of the Greene-Kleitman theorem
• The parameterized complexity landscape of two-sets cut-uncut
• Parallel complexity of geometric bipartite matching
• When does FTP become FPT??
• Unbent collections of orthogonal drawings
• When does FTP become FPT?
• Connectivity-preserving minimum separator in AT-free graphs
• Compact representation of semilinear and terrain-like graphs
• Faster algorithm for second (s,t)-mincut and breaking quadratic barrier for dual edge sensitivity for (s,t)-mincut
• Bootstrapping dynamic apsp via sparsification

This page was built for publication: A deterministic almost-linear time algorithm for minimum-cost flow

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6942935)