{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2023,1,17]],"date-time":"2023-01-17T20:26:17Z","timestamp":1673987177912},"reference-count":44,"publisher":"Association for Computing Machinery (ACM)","license":[{"start":{"date-parts":[[2018,10,1]],"date-time":"2018-10-01T00:00:00Z","timestamp":1538352000000},"content-version":"vor","delay-in-days":0,"URL":"http:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["ACM J. Exp. Algorithmics"],"published-print":{"date-parts":[[2018,11,15]]},"abstract":"The minimum cut problem for an undirected edge-weighted graph asks us to divide its set of nodes into two blocks while minimizing the weight sum of the cut edges. Here, we introduce a linear-time algorithm to compute near-minimum cuts. Our algorithm is based on cluster contraction using label propagation and Padberg and Rinaldi\u2019s contraction heuristics [SIAM Review, 1991]. We give both sequential and shared-memory parallel implementations of our algorithm. Extensive experiments on both real-world and generated instances show that our algorithm finds the optimal cut on nearly all instances significantly faster than other state-of-the-art exact algorithms, and our error rate is lower than that of other heuristic algorithms. In addition, our parallel algorithm runs a factor 7.5\u00d7 faster on average when using 32 threads. To further speed up computations, we also give a version of our algorithm that performs random edge contractions as preprocessing. This version achieves a lower running time and better parallel scalability at the expense of a higher error rate.<\/jats:p>","DOI":"10.1145\/3274662","type":"journal-article","created":{"date-parts":[[2018,10,1]],"date-time":"2018-10-01T12:15:55Z","timestamp":1538396155000},"page":"1-22","source":"Crossref","is-referenced-by-count":5,"title":["Practical Minimum Cut Algorithms"],"prefix":"10.1145","volume":"23","author":[{"given":"Monika","family":"Henzinger","sequence":"first","affiliation":[{"name":"University of Vienna, Vienna, Austria"}]},{"ORCID":"http:\/\/orcid.org\/0000-0002-4711-3323","authenticated-orcid":false,"given":"Alexander","family":"Noe","sequence":"additional","affiliation":[{"name":"University of Vienna, Vienna, Austria"}]},{"given":"Christian","family":"Schulz","sequence":"additional","affiliation":[{"name":"University of Vienna, Vienna, Austria"}]},{"given":"Darren","family":"Strash","sequence":"additional","affiliation":[{"name":"Hamilton College, Clinton, NY, USA"}]}],"member":"320","published-online":{"date-parts":[[2018,10]]},"reference":[{"key":"e_1_2_1_1_1","volume-title":"2015 Proceedings of the 17th Workshop on Algorithm Engineering and Experiments (ALENEX\u201914)","author":"Akhremtsev Yaroslav","year":"2014","unstructured":"Yaroslav Akhremtsev , Peter Sanders , and Christian Schulz . 2014 . (Semi-) external algorithms for graph partitioning and clustering . In 2015 Proceedings of the 17th Workshop on Algorithm Engineering and Experiments (ALENEX\u201914) . SIAM, 33--43. Yaroslav Akhremtsev, Peter Sanders, and Christian Schulz. 2014. (Semi-) external algorithms for graph partitioning and clustering. In 2015 Proceedings of the 17th Workshop on Algorithm Engineering and Experiments (ALENEX\u201914). SIAM, 33--43."},{"key":"e_1_2_1_2_1","unstructured":"Yaroslav Akhremtsev Peter Sanders and Christian Schulz. 2017. High-quality shared-memory graph partitioning. arXiv preprint arXiv:1710.08231. Yaroslav Akhremtsev Peter Sanders and Christian Schulz. 2017. High-quality shared-memory graph partitioning. arXiv preprint arXiv:1710.08231."},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/103418.103458"},{"key":"e_1_2_1_4_1","doi-asserted-by":"crossref","unstructured":"D. Bader A. Kappes H. Meyerhenke P. Sanders C. Schulz and D. Wagner. 2014. Benchmarking for graph clustering and partitioning. In Encyclopedia of Social Network Analysis and Mining Reda Alhajj and Jon Rokne (Eds.). Springer 1--11. D. Bader A. Kappes H. Meyerhenke P. Sanders C. Schulz and D. Wagner. 2014. Benchmarking for graph clustering and partitioning. In Encyclopedia of Social Network Analysis and Mining Reda Alhajj and Jon Rokne (Eds.). Springer 1--11.","DOI":"10.1007\/978-1-4614-7163-9_23-1"},{"key":"e_1_2_1_5_1","unstructured":"Vladimir Batagelj and Matjaz Zaversnik. 2003. An O(m) algorithm for cores decomposition of networks. arXiv preprint cs\/0310049. Vladimir Batagelj and Matjaz Zaversnik. 2003. An O ( m ) algorithm for cores decomposition of networks. arXiv preprint cs\/0310049."},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/1963405.1963488"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/988672.988752"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/1132952.1132954"},{"key":"e_1_2_1_9_1","volume-title":"Proceedings of the 8th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA\u201997)","author":"Chekuri Chandra S.","year":"1997","unstructured":"Chandra S. Chekuri , Andrew V. Goldberg , David R. Karger , Matthew S. Levine , and Cliff Stein . 1997 . Experimental study of minimum cut algorithms . In Proceedings of the 8th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA\u201997) . SIAM, 324--333. Chandra S. Chekuri, Andrew V. Goldberg, David R. Karger, Matthew S. Levine, and Cliff Stein. 1997. Experimental study of minimum cut algorithms. In Proceedings of the 8th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA\u201997). SIAM, 324--333."},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1109\/99.660313"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.4153\/CJM-1956-045-5"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/364099.364331"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/3178487.3178504"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/48014.61051"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1137\/0109047"},{"key":"e_1_2_1_16_1","volume-title":"Orlin","author":"Hao Jianxiu","year":"1992","unstructured":"Jianxiu Hao and James B . Orlin . 1992 . A faster algorithm for finding the minimum cut in a graph. In Proceedings of the 3rd Annual ACM-SIAM Symposium on Discrete Algorithms. SIAM , 165--174. Jianxiu Hao and James B. Orlin. 1992. A faster algorithm for finding the minimum cut in a graph. In Proceedings of the 3rd Annual ACM-SIAM Symposium on Discrete Algorithms. SIAM, 165--174."},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.5555\/3039686.3039811"},{"key":"e_1_2_1_18_1","unstructured":"Pili Hu and Wing Cheong Lau. 2013. A survey and taxonomy of graph sampling. arXiv preprint arXiv:1308.5865. Pili Hu and Wing Cheong Lau. 2013. A survey and taxonomy of graph sampling. arXiv preprint arXiv:1308.5865."},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1007\/s004539910009"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/331605.331608"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0036144501387141"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/234533.234534"},{"key":"e_1_2_1_23_1","volume-title":"Metis: A software package for partitioning unstructured graphs, partitioning meshes, and computing fill-reducing orderings of sparse matrices, Version 4.","author":"Karypis George","year":"1998","unstructured":"George Karypis and Vipin Kumar . 1998 . Metis: A software package for partitioning unstructured graphs, partitioning meshes, and computing fill-reducing orderings of sparse matrices, Version 4. George Karypis and Vipin Kumar. 1998. Metis: A software package for partitioning unstructured graphs, partitioning meshes, and computing fill-reducing orderings of sparse matrices, Version 4."},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/2746539.2746588"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1109\/PACT.2015.15"},{"key":"e_1_2_1_26_1","series-title":"Lecture Notes in Computer Science","volume-title":"Proceedings of the 14th International Conference on Distributed Computing and Networking (ICDCN\u20193)","author":"Kothapalli Kishore","unstructured":"Kishore Kothapalli , Sriram V. Pemmaraju , and Vivek Sardeshmukh . 2013. On the analysis of a label propagation algorithm for community detection . In Proceedings of the 14th International Conference on Distributed Computing and Networking (ICDCN\u20193) , Lecture Notes in Computer Science , Vol. 7730 . Springer , 255--269. Kishore Kothapalli, Sriram V. Pemmaraju, and Vivek Sardeshmukh. 2013. On the analysis of a label propagation algorithm for community detection. In Proceedings of the 14th International Conference on Distributed Computing and Networking (ICDCN\u20193), Lecture Notes in Computer Science, Vol. 7730. Springer, 255--269."},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevE.82.036106"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1109\/TC.1984.1676460"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1145\/2851141.2851188"},{"key":"e_1_2_1_30_1","volume-title":"Proceedings of the 4th Annual ACM-SIAM Symposium on Discrete Algorithms. SIAM, 500--504","author":"Matula David W.","year":"1993","unstructured":"David W. Matula . 1993 . A linear time 2+ϵ approximation algorithm for edge connectivity . In Proceedings of the 4th Annual ACM-SIAM Symposium on Discrete Algorithms. SIAM, 500--504 . David W. Matula. 1993. A linear time 2+ϵ approximation algorithm for edge connectivity. In Proceedings of the 4th Annual ACM-SIAM Symposium on Discrete Algorithms. SIAM, 500--504."},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1137\/0405004"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01582226"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01580850"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1137\/1033004"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevE.76.036106"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.5555\/2794560.3113630"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1007\/11427186_54"},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1016\/0378-8733(83)90028-X"},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICPP.2013.27"},{"key":"e_1_2_1_41_1","unstructured":"Christian L. Staudt Aleksejs Sazonovs and Henning Meyerhenke. 2014. NetworKit: An interactive tool suite for high-performance network analysis. CoRR abs\/1403.3005. Christian L. Staudt Aleksejs Sazonovs and Henning Meyerhenke. 2014. NetworKit: An interactive tool suite for high-performance network analysis. CoRR abs\/1403.3005."},{"key":"e_1_2_1_42_1","volume-title":"Minimum cut code. Retrieved","author":"Stein Clifford","year":"2017","unstructured":"Clifford Stein and Matthew Levine . Minimum cut code. Retrieved June 9, 2017 from http:\/\/www.columbia.edu\/∼cs2035\/code.html. Clifford Stein and Matthew Levine. Minimum cut code. Retrieved June 9, 2017 from http:\/\/www.columbia.edu\/∼cs2035\/code.html."},{"key":"e_1_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1145\/263867.263872"},{"key":"e_1_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-48971-0_40"},{"key":"e_1_2_1_45_1","volume-title":"EEF Summer School on Massive Data Sets. Retrieved","author":"Zeh Norbert","year":"2002","unstructured":"Norbert Zeh . 2002 . I\/O-efficient graph algorithms . EEF Summer School on Massive Data Sets. Retrieved June 11, 2018 from https:\/\/www.cs.au.dk\/∼gerth\/MassiveData02\/notes\/zeh.pdf. (2002). Norbert Zeh. 2002. I\/O-efficient graph algorithms. EEF Summer School on Massive Data Sets. Retrieved June 11, 2018 from https:\/\/www.cs.au.dk\/∼gerth\/MassiveData02\/notes\/zeh.pdf. (2002)."}],"container-title":["ACM Journal of Experimental Algorithmics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3274662","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,1,1]],"date-time":"2023-01-01T13:26:15Z","timestamp":1672579575000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3274662"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018,10]]},"references-count":44,"alternative-id":["10.1145\/3274662"],"URL":"http:\/\/dx.doi.org\/10.1145\/3274662","relation":{},"ISSN":["1084-6654","1084-6654"],"issn-type":[{"value":"1084-6654","type":"print"},{"value":"1084-6654","type":"electronic"}],"subject":["Theoretical Computer Science"],"published":{"date-parts":[[2018,10]]}}}