An <i>Õ(n<sup>2</sup>)</i> algorithm for minimum cuts
Published 1 January 1993
David R. Karger, Clifford Stein
Citations73
Generate an AI Snapshot to get a quick, structured summary of this paper.
Study Snapshot
ObjectiveStudy objective
MethodsResearch methodology
PopulationPopulation studied
Sample sizeSample sizes
OutcomesStudy outcomes here
ResultsStudy results comes here
LimitationsResearch study limitations comes here
A concise AI-generated summary of the paper will appear here once you click Generate AI Snapshot.
TL;DR
This paper presents the first algorithm that breaks the tl(mn) “max-flow barrier” for finding minimum cuts in weighted undirected graphs by giving a strongly polynomial randomized algorithm which finds a minimum cut with high probability in 0(n2 log3 n) time.
Abstract
Article An Õ(n2) algorithm for minimum cuts Share on Authors: David R. Karger View Profile , Clifford Stein View Profile Authors Info & Claims STOC '93: Proceedings of the twenty-fifth annual ACM symposium on Theory of ComputingJune 1993 Pages 757–765https://doi.org/10.1145/167088.167281Online:01 June 1993Publication History 35citation853DownloadsMetricsTotal Citations35Total Downloads853Last 12 Months22Last 6 weeks3 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteGet Access
Keywords
Computer ScienceDecision Sciences
Flows in networks
4,080 Citations1962D. R. Ford, D. R. Fulkerson
Journal of the ACMTheoretical Improvements in Algorithmic Efficiency for Network Flow Problems
2,522 Citations1972Jack Edmonds, Richard M. Karp
Upper bounds on the number of steps in these algorithms are derived, and are shown to improve on the upper bounds of earlier algorithms.
Journal of the ACMA new approach to the maximum-flow problem
1,877 Citations1988Andrew V. Goldberg, Robert E. Tarjan
An alternative method based on the preflow concept of Karzanov, which runs as fast as any other known method on dense graphs, achieving an O(n) time bound on an n-vertex graph and faster on graphs of moderate density.
Birkhäuser Boston eBooksMaximal Flow Through a Network
1,856 Citations2009L. R. Ford, D. R. Fulkerson
Solution of a Large-Scale Traveling-Salesman Problem
1,273 Citations2009Vašek Chvátal, William J. Cook +3 more
The RAND Corporation in the early 1950s contained “what may have been the most remarkable group of mathematicians working on optimization ever assembled”: Arrow, Bellman, Dantzig, Flood, Ford, Fulkerson, Gale, Johnson, Nash, Orchard-Hays, Robinson, Shapley, Simon, Wagner, and other household names.
Matching is as easy as matrix inversion
617 Citations1987Ketan Mulmuley, Umesh Vazirani +1 more
A new algorithm for finding a maximum matching in a general graph with special feature is that its only computationally non-trivial step is the inversion of a single integer matrix, the isolating lemma.
SIAM Journal on Discrete MathematicsComputing Edge-Connectivity in Multigraphs and Capacitated Graphs
395 Citations1992Hiroshi Nagamochi, Toshihide Ibaraki
An algorithm for computing the edge-connectivity of a multigraph, where p ( \leqq | E | )$ is the number of pairs of nodes between which G has an edge, is proposed and consists only of times of graph searches and edge contractions.
COMBINATORICAConstructing a perfect matching is in random NC
254 Citations1986Richard M. Karp, Eli Upfal +1 more
A matroid approach to finding edge connectivity and packing arborescences
199 Citations1991Harold N. Gabow
An algorithm that finds k edge-disjoint arborescences on a directed graph in time O(kmn + k3n2)2 is presented, based on two theorems of Edmonds that link these two problems and show how they can be solved.
Journal of AlgorithmsA Faster Deterministic Maximum Flow Algorithm
193 Citations1994Valerie King, Satish Rao +1 more
A deterministic version of a 1990 Cheriyan, Hagerup, and Mehlhorn randomized algorithm for computing the maximum flow on a directed graph which runs in time improves upon Alon's 1989 bound and matches the 1988 algorithm of Goldberg and Tarjan for smaller values of m/n.
SIAM Journal on ComputingFaster Approximation Algorithms For the Unit Capacity Concurrent Flow Problem with Applications to Routing and Finding Sparse Cuts
147 Citations1994Philip N. Klein, Serge Plotkin +2 more
New algorithms for approximately solving the concurrent multicommodity flow problem with uniform capacities are described, which are much faster than algorithms discovered previously.
Theoretical Computer ScienceThe maximum flow problem is log space complete for P
133 Citations1982Leslie M. Goldschlager, Ralph A. Shaw +1 more
It is shown that the problem is log space complete for deterministic polynomial time, so the maximum flow problem probably has no algorithm which needs only O(logk n) storage space for any constant k.
Mathematical ProgrammingAn efficient algorithm for the minimum capacity cut problem
131 Citations1990Manfred Padberg, Giovanni Rinaldi
This work presents an alternative algorithm with the same worst-case bound which is easier to implement and which was found empirically to be far superior to the standard algorithm.
INFOR Information Systems and Operational ResearchSelected Applications of Minimum Cuts in Networks
110 Citations1982Jean-Claude Picard, Maurice Queyranne
A review and a synthesis of applications of minimum cuts to a variety of combinatorial optimization problems, including linear and non-linear integer programming, problems in location theory, graph theory, sequencing and scheduling, and other areas are provided.
RePEc: Research Papers in EconomicsA faster algorithm for finding the minimum cut in a graph
102 Citations1992Jianxiu Hao, James B. Orlin
This work considers the problem of finding the minimum capacity cut in a network G with n nodes, and shows how to reduce theRunning time of these 2n - 2 maximum flow algorithms to the running time for solving a single maximum flow problem.
Determining edge connectivity in 0(nm)
87 Citations1987David W. Matula
An algorithm that determines the edge connectivity of an n-vertex m-edge graph G in O(nm) time is described and a refinement shows that the question as to whether a graph is k-edge connected can be determined in O (kn2), for dense graphs characterized by m = Ω(n2).
Online load balancing and network flow
55 Citations1993Steven Phillips, Jeffery Westbrook
Lecture notes in computer scienceRepresenting and enumerating edge connectivity cuts in RNC
36 Citations2005Dalit Naor, Vijay V. Vazirani
This paper presents a fast parallel algorithm for obtaining a succinct and algorithmically useful representation for an undirected edge-weighted graph and observes that for a unary weighted graph, the problems of counting and enumerating the connectivity cuts are in RNC.
Leighton-Rao might be practical: faster approximation algorithms for concurrent flow with uniform capacities
32 Citations1990Philip N. Klein, Clifford Stein +1 more
New algorithms for approximately solving the concurrent multicommodity flow problem with uniform capacities are described, much faster than previously known algorithms and significantly improve the time required for finding such approximately optimal solutions.