Deterministic min-cut in poly-logarithmic max-flows

DOI10.1109/FOCS46700.2020.00017MaRDI QIDQ6944040zbMATH OpenFDO

Authors Debmalya Panigrahi, Jason Li

Publication date 12 August 2025

Full work available at URL https://doi.org/10.1109/FOCS46700.2020.00017

Mathematics Subject Classification ID

Proceedings, conferences, collections, etc. pertaining to computer science (68-06)

Cited in

(9)

• A simple and fast algorithm for fair cuts
• Vertex connectivity in poly-logarithmic max-flows
• High-speed minimum cut approximation in dense graph using compacted pruned tree
• Maximum flow and minimum-cost flow in almost-linear time
• Faster algorithms for rooted connectivity in directed graphs
• Isolating cuts, (bi-)submodularity, and faster algorithms for connectivity
• Worst-case to expander-case reductions: derandomized and generalized
• Deterministic minimum Steiner cut in maximum flow time
• Faster algorithm for second (s,t)-mincut and breaking quadratic barrier for dual edge sensitivity for (s,t)-mincut

This page was built for publication: Deterministic min-cut in poly-logarithmic max-flows

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