A faster algorithm for finding the minimum cut in a graph

ABSTRACT

We consider the problem of finding the minimum capacity cut in a network G with n nodes. This problem has applications to network reliability and survivability and is useful in subroutines for other network optimization problems. One can use a maximum flow problem to find a minimum cut separating a designated source node s from a designated sink node t, and by varying the sink node one can find a minimum cut in G as a sequence of at most 2n - 2 maximum flow problems. We then show how to reduce the running time of these 2n - 2 maximum flow algorithms to the running time for solving a single maximum flow problem. The resulting running time is O(nm log n2/m) for finding the minimum cut in either a directed or undirected network. The algorithm also determines the arc connectivity of either a directed or undirected network in O(nm) steps.

REFERENCES

• 1: Ravindra K. Ahuja , Thomas L. Magnanti , James B. Orlin, Network flows: theory, algorithms, and applications, Prentice-Hall, Inc., Upper Saddle River, NJ, 1993
• 2: Ahuja, R. K., J. B. Orlin, C. Stein, and R. E. Tarjan. 1990. Improved Algorithms for Bipartite Network Flows. Accepted for publication by Mathematical Programming.
• 3: Cheriyan, J. and S. N. Maheshwari. 1987. Analysis of Preflow Push Algorithms for Maximum Network Flow. Technical report, Department of Computer Science and Engineering, Indian Institute of Technology, New Delhi, India.
• 4: Derigs, U., and W. Meier. 1988. Implementing Goldberg's Max-Flow Algorithm: A Computational Investigation. Technical Report, University of Bayreuth, West Germany.
• 5: Ford, L.R., Jr., and D. R. Fulkerson. 1956. Maximal Flow Through a Network. Canadian journal Math. 8, 399-404.
• 6: G. Gallo , M. D. Grigoriadis , R. E. Tarjan, A fast parametric maximum flow algorithm and applications, SIAM Journal on Computing, v.18 n.1, p.30-55, Feb. 1989 [doi>10.1137/0218003]
• 7: Andrew V. Goldberg , Robert E. Tarjan, A new approach to the maximum-flow problem, Journal of the ACM (JACM), v.35 n.4, p.921-940, Oct. 1988 [doi>10.1145/48014.61051]
• 8: King V, S. Rao, and R. E. Tarjan. 1991. A Faster Deterministic Max-flow Algorithm. Manuscript in preparation.
• 9: Matula, D. W. 1987. Determining Edge Connectivity in O(nm). Proceedings of the 28th Annual Symposium on Foundations of Computer Science. 249-251.
• 10: Mansour, Y and B. Schieber. 1988. Finding the Edge Connectivity of Directed Graphs. Research Report RC 13556, IBM Research Division, T. j. Watson Research Center, Yorktown Heights, N.Y.
• 11: M. Padberg , G. Rinaldi, An efficient algorithm for the minimum capacity cut problem, Mathematical Programming: Series A and B, v.47 n.1, p.19-36, May 1990 [doi>10.1007/BF01580850]
• 12: Picard, J. C. and M. Queyranne. 1982. Selected applications of minimumcuts in networks. INFOR 20, 394-422.

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.2 Graph Theory
          Subjects: Network problems

General Terms:
Algorithms, Theory, Verification