A Faster Algorithm for Finding the Minimum Cut in a Directed Graph. Hao, J. X. & Orlin, J. B. J Algorithms, 17(3):424–446, 1994.
A Faster Algorithm for Finding the Minimum Cut in a Directed Graph [link]Paper  doi  abstract   bibtex   
We consider the problem of finding the minimum capacity cut in a directed 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 an undirected network.
@Article{hao94faster,
  author   = {J. X. Hao and J. B. Orlin},
  title    = {A Faster Algorithm for Finding the Minimum Cut in a Directed Graph},
  journal  = {J Algorithms},
  year     = {1994},
  volume   = {17},
  number   = {3},
  pages    = {424--446},
  issn     = {0196-6774},
  abstract = {We consider the problem of finding the minimum capacity cut in a directed 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 an undirected network.},
  doi      = {DOI: 10.1006/jagm.1994.1043},
  keywords = {min cut, max flow},
  url      = {http://www.sciencedirect.com/science/article/B6WH3-45NJXDC-7/2/59238e9f4cfe2185b5aae66c85cbf869},
}

Downloads: 0