A new approach to the minimum cut problem. Karger, D. R. & Stein, C. J ACM, 43(4):601–640, ACM press, New York, New York, NY, USA, 1996. doi abstract bibtex This paper present a new approach to finding minimum cuts in undirected graphs. The fundamental principle is simple: the edges in a graph's minimum cut form an extremely small fraction of the graph's edges. Using this idea, we give a randomized, strongly polynomial algorithm that finds the minimum cut in an arbitrarily weighted undirected graph with high probability. The algorithm runs in $O(n^2 log^3 n)$ time, a significant improvement over the previous $O~(mn)$ time bounds based on maximum flows. It is simple and intuitive and uses no complex data structures. Our algorithm can be parallelized to run in RNC with $n^2$ processors; this gives the first proof that the minimum cut problem can be solved in RNC. The algorithm does more than find a single minimum cut; it finds all of them.With minor modifications, our algorithm solves two other problems of interest. Our algorithm finds all cuts with value within a multiplicative factor of alpha of the minimum cut's in expected $O~(n^{2α})$ time, or in RNC with $2^{2α}$ processors. The problem of finding a minimum multiway cut of graph into r pieces is solved in expected $O~(n^{2(r-1)})$ time, or in RNC with $n^{2(r-1)}$ processors. The ``trace'' of the algorithm's execution on these two problems forms a new compact data structure for representing all small cuts and all multiway cuts in a graph. This data structure can be efficiently transformed into the more standard cactus representing for minimum cuts.
@Article{karger96new,
author = {Karger, David R. and Stein, Clifford},
title = {A new approach to the minimum cut problem},
journal = {J ACM},
year = {1996},
volume = {43},
number = {4},
pages = {601--640},
issn = {0004-5411},
abstract = {This paper present a new approach to finding minimum cuts in undirected graphs. The fundamental principle is simple: the edges in a graph's minimum cut form an extremely small fraction of the graph's edges. Using this idea, we give a randomized, strongly polynomial algorithm that finds the minimum cut in an arbitrarily weighted undirected graph with high probability. The algorithm runs in $O(n^2 log^3 n)$ time, a significant improvement over the previous $O~(mn)$ time bounds based on maximum flows. It is simple and intuitive and uses no complex data structures. Our algorithm can be parallelized to run in RNC with $n^2$ processors; this gives the first proof that the minimum cut problem can be solved in RNC. The algorithm does more than find a single minimum cut; it finds all of them.With minor modifications, our algorithm solves two other problems of interest. Our algorithm finds all cuts with value within a multiplicative factor of alpha of the minimum cut's in expected $O~(n^{2\alpha})$ time, or in RNC with $2^{2\alpha}$ processors. The problem of finding a minimum multiway cut of graph into r pieces is solved in expected $O~(n^{2(r-1)})$ time, or in RNC with $n^{2(r-1)}$ processors. The ``trace'' of the algorithm's execution on these two problems forms a new compact data structure for representing all small cuts and all multiway cuts in a graph. This data structure can be efficiently transformed into the more standard cactus representing for minimum cuts.},
address = {New York, NY, USA},
doi = {10.1145/234533.234534},
owner = {Sebastian},
publisher = {ACM press, New York},
timestamp = {2010.07.04},
}
Downloads: 0
{"_id":"h7zeuXHv78McuKQpr","bibbaseid":"karger-stein-anewapproachtotheminimumcutproblem-1996","authorIDs":[],"author_short":["Karger, D. R.","Stein, C."],"bibdata":{"bibtype":"article","type":"article","author":[{"propositions":[],"lastnames":["Karger"],"firstnames":["David","R."],"suffixes":[]},{"propositions":[],"lastnames":["Stein"],"firstnames":["Clifford"],"suffixes":[]}],"title":"A new approach to the minimum cut problem","journal":"J ACM","year":"1996","volume":"43","number":"4","pages":"601–640","issn":"0004-5411","abstract":"This paper present a new approach to finding minimum cuts in undirected graphs. The fundamental principle is simple: the edges in a graph's minimum cut form an extremely small fraction of the graph's edges. Using this idea, we give a randomized, strongly polynomial algorithm that finds the minimum cut in an arbitrarily weighted undirected graph with high probability. The algorithm runs in $O(n^2 log^3 n)$ time, a significant improvement over the previous $O~(mn)$ time bounds based on maximum flows. It is simple and intuitive and uses no complex data structures. Our algorithm can be parallelized to run in RNC with $n^2$ processors; this gives the first proof that the minimum cut problem can be solved in RNC. The algorithm does more than find a single minimum cut; it finds all of them.With minor modifications, our algorithm solves two other problems of interest. Our algorithm finds all cuts with value within a multiplicative factor of alpha of the minimum cut's in expected $O~(n^{2α})$ time, or in RNC with $2^{2α}$ processors. The problem of finding a minimum multiway cut of graph into r pieces is solved in expected $O~(n^{2(r-1)})$ time, or in RNC with $n^{2(r-1)}$ processors. The ``trace'' of the algorithm's execution on these two problems forms a new compact data structure for representing all small cuts and all multiway cuts in a graph. This data structure can be efficiently transformed into the more standard cactus representing for minimum cuts.","address":"New York, NY, USA","doi":"10.1145/234533.234534","owner":"Sebastian","publisher":"ACM press, New York","timestamp":"2010.07.04","bibtex":"@Article{karger96new,\n author = {Karger, David R. and Stein, Clifford},\n title = {A new approach to the minimum cut problem},\n journal = {J ACM},\n year = {1996},\n volume = {43},\n number = {4},\n pages = {601--640},\n issn = {0004-5411},\n abstract = {This paper present a new approach to finding minimum cuts in undirected graphs. The fundamental principle is simple: the edges in a graph's minimum cut form an extremely small fraction of the graph's edges. Using this idea, we give a randomized, strongly polynomial algorithm that finds the minimum cut in an arbitrarily weighted undirected graph with high probability. The algorithm runs in $O(n^2 log^3 n)$ time, a significant improvement over the previous $O~(mn)$ time bounds based on maximum flows. It is simple and intuitive and uses no complex data structures. Our algorithm can be parallelized to run in RNC with $n^2$ processors; this gives the first proof that the minimum cut problem can be solved in RNC. The algorithm does more than find a single minimum cut; it finds all of them.With minor modifications, our algorithm solves two other problems of interest. Our algorithm finds all cuts with value within a multiplicative factor of alpha of the minimum cut's in expected $O~(n^{2\\alpha})$ time, or in RNC with $2^{2\\alpha}$ processors. The problem of finding a minimum multiway cut of graph into r pieces is solved in expected $O~(n^{2(r-1)})$ time, or in RNC with $n^{2(r-1)}$ processors. The ``trace'' of the algorithm's execution on these two problems forms a new compact data structure for representing all small cuts and all multiway cuts in a graph. This data structure can be efficiently transformed into the more standard cactus representing for minimum cuts.},\n address = {New York, NY, USA},\n doi = {10.1145/234533.234534},\n owner = {Sebastian},\n publisher = {ACM press, New York},\n timestamp = {2010.07.04},\n}\n\n","author_short":["Karger, D. R.","Stein, C."],"key":"karger96new","id":"karger96new","bibbaseid":"karger-stein-anewapproachtotheminimumcutproblem-1996","role":"author","urls":{},"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.197Z","downloads":0,"keywords":[],"search_terms":["new","approach","minimum","cut","problem","karger","stein"],"title":"A new approach to the minimum cut problem","year":1996,"dataSources":["C5FtkvWWggFfMJTFX"]}