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]](https://bibbase.org/img/filetypes/link.svg "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
{"_id":"smDj8ZeHqKB323agN","bibbaseid":"hao-orlin-afasteralgorithmforfindingtheminimumcutinadirectedgraph-1994","authorIDs":[],"author_short":["Hao, J. X.","Orlin, J. B."],"bibdata":{"bibtype":"article","type":"article","author":[{"firstnames":["J.","X."],"propositions":[],"lastnames":["Hao"],"suffixes":[]},{"firstnames":["J.","B."],"propositions":[],"lastnames":["Orlin"],"suffixes":[]}],"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","bibtex":"@Article{hao94faster,\n author = {J. X. Hao and J. B. Orlin},\n title = {A Faster Algorithm for Finding the Minimum Cut in a Directed Graph},\n journal = {J Algorithms},\n year = {1994},\n volume = {17},\n number = {3},\n pages = {424--446},\n issn = {0196-6774},\n 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.},\n doi = {DOI: 10.1006/jagm.1994.1043},\n keywords = {min cut, max flow},\n url = {http://www.sciencedirect.com/science/article/B6WH3-45NJXDC-7/2/59238e9f4cfe2185b5aae66c85cbf869},\n}\n\n","author_short":["Hao, J. X.","Orlin, J. B."],"key":"hao94faster","id":"hao94faster","bibbaseid":"hao-orlin-afasteralgorithmforfindingtheminimumcutinadirectedgraph-1994","role":"author","urls":{"Paper":"http://www.sciencedirect.com/science/article/B6WH3-45NJXDC-7/2/59238e9f4cfe2185b5aae66c85cbf869"},"keyword":["min cut","max flow"],"metadata":{"authorlinks":{}}},"bibtype":"article","biburl":"https://git.bio.informatik.uni-jena.de/fleisch/literature/raw/master/group-literature.bib","creationDate":"2019-11-19T16:50:42.061Z","downloads":0,"keywords":["min cut","max flow"],"search_terms":["faster","algorithm","finding","minimum","cut","directed","graph","hao","orlin"],"title":"A Faster Algorithm for Finding the Minimum Cut in a Directed Graph","year":1994,"dataSources":["C5FtkvWWggFfMJTFX"]}