An Õ(n2) algorithm for minimum cuts

DOI10.1145/167088.167281zbMath1310.05200OpenAlexW2009339416MaRDI QIDQ5248547

David R. Karger, Clifford Stein

Publication date: 7 May 2015

Published in: Proceedings of the twenty-fifth annual ACM symposium on Theory of computing - STOC '93 (Search for Journal in Brave)

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

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph algorithms (graph-theoretic aspects) (05C85) Randomized algorithms (68W20)

Related Items

Logical s-t Min-Cut Problem: An Extension to the Classic s-t Min-Cut Problem, A new unifying heuristic algorithm for the undirected minimum cut problems using minimum range cut algorithms, Efficient algorithms for minimum range cut problems, Finding real-valued single-source shortest paths in o(n 3) expected time, Graph connectivity and its augmentation: Applications of MA orderings, Implementing an efficient minimum capacity cut algorithm, On the number of small cut in a graph, Fast Augmenting Paths by Random Sampling from Residual Graphs