New Algorithms and Lower Bounds for All-Pairs Max-Flow in Undirected Graphs

DOI10.1137/1.9781611975994.4MaRDI QIDQ5146764zbMATH OpenOpenAlexFDO

Authors Amir Abboud, Robert Krauthgamer, Ohad Trabelsi

Publication date 2 February 2021

Published in Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1137/1.9781611975994.4

Mathematics Subject Classification ID

Algorithms in computer science (68Wxx)

Recommendations

• New algorithms and lower bounds for all-pairs max-flow in undirected graphs
• Conditional Lower Bounds for All-Pairs Max-Flow
• scientific article; zbMATH DE number 7204472
• Faster algorithms for all-pairs bounded min-cuts
• Breaking the \(O(n^{2.5})\) deterministic time barrier for undirected unit-capacity maximum flow

Cited in

(8)

• Speeding up the Gomory-Hu parallel cut tree algorithm with efficient graph contractions
• Conditional Lower Bounds for All-Pairs Max-Flow
• Faster algorithms for all-pairs bounded min-cuts
• New algorithms and lower bounds for all-pairs max-flow in undirected graphs
• Some insights on dynamic maintenance of Gomory-Hu tree in cactus graphs and general graphs
• Tight conditional lower bounds for vertex connectivity problems
• Approximate Gomory-Hu tree is faster than \(n-1\) maximum flows
• Hardness of approximate diameter: now for undirected graphs

This page was built for publication: New Algorithms and Lower Bounds for All-Pairs Max-Flow in Undirected Graphs

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