Deterministic minimum cut in poly-logarithmic maximum flows

DOI10.1145/3744737MaRDI QIDQ6912092zbMATH OpenFDO

Authors Jason Li, Debmalya Panigrahi

Publication date 23 October 2025

Published in Journal of the ACM (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://doi.org/10.1145/3744737

zbMATH Keywords

isolating cutsminimum cut algorithm

Mathematics Subject Classification ID

Flows in graphs (05C21) Connectivity (05C40) Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Randomized algorithms (68W20)

Cites work

• A deterministic almost-linear time algorithm for minimum-cost flow
• A fast algorithm for computing steiner edge connectivity
• A linear-time algorithm for finding a sparse \(k\)-connected spanning subgraph of a \(k\)-connected graph
• A matroid approach to finding edge connectivity and packing arborescences
• A new approach to the maximum-flow problem
• A new approach to the minimum cut problem
• A simple min-cut algorithm
• An Õ(mn) Gomory-Hu tree construction algorithm for unweighted graphs
• Approximate Gomory–Hu tree is faster than n – 1 max-flows
• Augmenting edge connectivity via isolating cuts
• Beyond the flow decomposition barrier
• Breaking the cubic barrier for all-pairs max-flow: Gomory-Hu tree in nearly quadratic time
• Color-coding
• Computing Edge-Connectivity in Multigraphs and Capacitated Graphs
• Deterministic Edge Connectivity in Near-Linear Time
• Deterministic near-linear time minimum cut in weighted graphs
• Edge connectivity augmentation in near-linear time
• Efficient algorithms for computing all low s-t edge connectivities and related problems
• Faster cut-equivalent trees in simple graphs
• scientific article; zbMATH DE number 437525 (Why is no real title available?)
• scientific article; zbMATH DE number 5764893 (Why is no real title available?)
• scientific article; zbMATH DE number 742961 (Why is no real title available?)
• Local flow partitioning for faster edge connectivity
• Minimum cuts in near-linear time
• Multi-Terminal Network Flows
• Parameterized algorithms
• Subcubic algorithms for Gomory–Hu tree in unweighted graphs
• The connectivity carcass of a vertex subset in a graph and its incremental maintenance
• Vertex connectivity in poly-logarithmic max-flows

Cited in

(1)

• Space complexity of vertex connectivity oracles

This page was built for publication: Deterministic minimum cut in poly-logarithmic maximum flows

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