{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,10]],"date-time":"2026-06-10T07:57:04Z","timestamp":1781078224528,"version":"3.54.1"},"reference-count":31,"publisher":"Association for Computing Machinery (ACM)","issue":"1","license":[{"start":{"date-parts":[[2018,12,12]],"date-time":"2018-12-12T00:00:00Z","timestamp":1544572800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/100008398","name":"VILLUM Foundation","doi-asserted-by":"crossref","id":[{"id":"10.13039\/100008398","id-type":"DOI","asserted-by":"crossref"}]},{"name":"JSPS KAKENHI","award":["JP18H05291"],"award-info":[{"award-number":["JP18H05291"]}]},{"DOI":"10.13039\/501100004836","name":"Danish Council for Independent Research","doi-asserted-by":"crossref","award":["DFF-0602-02499B"],"award-info":[{"award-number":["DFF-0602-02499B"]}],"id":[{"id":"10.13039\/501100004836","id-type":"DOI","asserted-by":"crossref"}]},{"name":"JST ERATO Kawarabayashi Large Graph Project","award":["JPMJER1201"],"award-info":[{"award-number":["JPMJER1201"]}]},{"name":"Basic Algorithms Research Copenhage"},{"name":"Investigator Grant","award":["16582"],"award-info":[{"award-number":["16582"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["J. ACM"],"published-print":{"date-parts":[[2019,2,28]]},"abstract":"<jats:p>\n            We present a deterministic algorithm that computes the edge-connectivity of a graph in near-linear time. This is for a simple undirected unweighted graph\n            <jats:italic>G<\/jats:italic>\n            with\n            <jats:italic>n<\/jats:italic>\n            vertices and\n            <jats:italic>m<\/jats:italic>\n            edges. This is the first\n            <jats:italic>o<\/jats:italic>\n            (\n            <jats:italic>mn<\/jats:italic>\n            ) time deterministic algorithm for the problem. Our algorithm is easily extended to find a concrete minimum edge-cut. In fact, we can construct the classic cactus representation of all minimum cuts in near-linear time.\n          <\/jats:p>\n          <jats:p>\n            The previous fastest deterministic algorithm by Gabow from STOC '91 took \u00d5(\n            <jats:italic>m<\/jats:italic>\n            +\u03bb\n            <jats:sup>2<\/jats:sup>\n            <jats:italic>n<\/jats:italic>\n            ), where \u03bb is the edge connectivity, but \u03bb can be as big as\n            <jats:italic>n<\/jats:italic>\n            \u22121. Karger presented a randomized near-linear time Monte Carlo algorithm for the minimum cut problem at STOC\u201996, but the returned cut is only minimum with high probability.\n          <\/jats:p>\n          <jats:p>\n            Our main technical contribution is a near-linear time algorithm that contracts vertex sets of a simple input graph\n            <jats:italic>G<\/jats:italic>\n            with minimum degree \u0394, producing a multigraph \u1e20 with \u00d5(\n            <jats:italic>m<\/jats:italic>\n            \/\u0394) edges, which preserves all minimum cuts of\n            <jats:italic>G<\/jats:italic>\n            with at least two vertices on each side.\n          <\/jats:p>\n          <jats:p>In our deterministic near-linear time algorithm, we will decompose the problem via low-conductance cuts found using PageRank a la Brin and Page (1998), as analyzed by Andersson, Chung, and Lang at FOCS\u201906. Normally, such algorithms for low-conductance cuts are randomized Monte Carlo algorithms, because they rely on guessing a good start vertex. However, in our case, we have so much structure that no guessing is needed.<\/jats:p>","DOI":"10.1145\/3274663","type":"journal-article","created":{"date-parts":[[2018,12,12]],"date-time":"2018-12-12T12:49:32Z","timestamp":1544618972000},"page":"1-50","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":32,"title":["Deterministic Edge Connectivity in Near-Linear Time"],"prefix":"10.1145","volume":"66","author":[{"given":"Ken-Ichi","family":"Kawarabayashi","sequence":"first","affiliation":[{"name":"National Institute of Informatics, Chiyoda-ku, Tokyo, Japan"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Mikkel","family":"Thorup","sequence":"additional","affiliation":[{"name":"BARC, University of Copenhagen, Denmark"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2018,12,12]]},"reference":[{"key":"e_1_2_1_1_1","volume-title":"Proceedings of the 4th TAMC. 1--12","author":"Andersen Reid","unstructured":"Reid Andersen and Fan R. K. Chung . 2007. Detecting sharp drops in PageRank and a simplified local partitioning algorithm . In Proceedings of the 4th TAMC. 1--12 . Reid Andersen and Fan R. K. Chung. 2007. Detecting sharp drops in PageRank and a simplified local partitioning algorithm. In Proceedings of the 4th TAMC. 1--12."},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1080\/15427951.2007.10129139"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0169-7552(98)00110-X"},{"key":"e_1_2_1_4_1","volume-title":"Proceedings of the 15th SODA. 828--829","author":"Chalermsook P.","unstructured":"P. Chalermsook , J. Fakcharoenphol , and D. Nanongkai . 2004. A deterministic near-linear time algorithm for finding minimum cuts in planar graphs . In Proceedings of the 15th SODA. 828--829 . P. Chalermsook, J. Fakcharoenphol, and D. Nanongkai. 2004. A deterministic near-linear time algorithm for finding minimum cuts in planar graphs. In Proceedings of the 15th SODA. 828--829."},{"key":"e_1_2_1_5_1","volume-title":"Lomonosov","author":"Dinitz Efim A.","year":"1976","unstructured":"Efim A. Dinitz , A. V. Karzanov , and Micael V . Lomonosov . 1976 . A structure of the system of all minimum cuts of a graph. In Studies in Discrete Optimization, A.A. Fridman (Ed .). 290--306. Efim A. Dinitz, A. V. Karzanov, and Micael V. Lomonosov. 1976. A structure of the system of all minimum cuts of a graph. In Studies in Discrete Optimization, A.A. Fridman (Ed.). 290--306."},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1137\/0204043"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.4153\/CJM-1956-045-5"},{"key":"e_1_2_1_8_1","unstructured":"A. Frank. 1994. On the edge-connectivity algorithm of Nagamochi and Ibaraki. Laboratoire Artemis IMAG Universite J. Fourier Grenoble. http:\/\/web.cs.elte.hu\/&sim;frank\/cikkek\/FrankR2.pdf.  A. Frank. 1994. On the edge-connectivity algorithm of Nagamochi and Ibaraki. Laboratoire Artemis IMAG Universite J. Fourier Grenoble. http:\/\/web.cs.elte.hu\/&sim;frank\/cikkek\/FrankR2.pdf."},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.1995.1022"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/2764909"},{"key":"e_1_2_1_11_1","first-page":"551","article-title":"Multi-terminal network flows","volume":"9","author":"Gomory R. E.","year":"1961","unstructured":"R. E. Gomory and T. C. Hu . 1961 . Multi-terminal network flows . J. SIAM 9 , 4 (1961), 551 -- 570 . R. E. Gomory and T. C. Hu. 1961. Multi-terminal network flows. J. SIAM 9, 4 (1961), 551--570.","journal-title":"J. SIAM"},{"key":"e_1_2_1_12_1","volume-title":"Proceedings of the 24th ESA. 46:1--46:17","author":"Goranci G.","unstructured":"G. Goranci , M. Henzinger , and M. Thorup . 2016. Incremental exact min-cut in poly-logarithmic amortized update time . In Proceedings of the 24th ESA. 46:1--46:17 . G. Goranci, M. Henzinger, and M. Thorup. 2016. Incremental exact min-cut in poly-logarithmic amortized update time. In Proceedings of the 24th ESA. 46:1--46:17."},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1006\/jagm.1994.1043"},{"key":"e_1_2_1_14_1","volume-title":"Proceedings of the 28th SODA. 1919--1938","author":"Henzinger M.","unstructured":"M. Henzinger , S. Rao , and D. Wang . 2017. Local flow partitioning for faster edge connectivity . In Proceedings of the 28th SODA. 1919--1938 . M. Henzinger, S. Rao, and D. Wang. 2017. Local flow partitioning for faster edge connectivity. In Proceedings of the 28th SODA. 1919--1938."},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(96)00079-8"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/502090.502095"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1287\/moor.24.2.383"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/331605.331608"},{"key":"e_1_2_1_19_1","volume-title":"Proceedings of the 20th SODA. 246--255","author":"David","unstructured":"David R. Karger and Debmalya Panigrahi. 2009. A near-linear time algorithm for constructing a cactus representation of minimum cuts . In Proceedings of the 20th SODA. 246--255 . David R. Karger and Debmalya Panigrahi. 2009. A near-linear time algorithm for constructing a cactus representation of minimum cuts. In Proceedings of the 20th SODA. 246--255."},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/234533.234534"},{"key":"e_1_2_1_21_1","first-page":"8","article-title":"Efficient algorithm for finding all minimal edge cuts of a nonoriented graph","volume":"2","author":"Karzanov A. V.","year":"1986","unstructured":"A. V. Karzanov and E. A. Timofeev . 1986 . Efficient algorithm for finding all minimal edge cuts of a nonoriented graph . Kibernetika 2 (1986), 8 -- 12 ; translated in Cybernetics (1986), pp. 156--162. A. V. Karzanov and E. A. Timofeev. 1986. Efficient algorithm for finding all minimal edge cuts of a nonoriented graph. Kibernetika 2 (1986), 8--12; translated in Cybernetics (1986), pp. 156--162.","journal-title":"Kibernetika"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/2746539.2746588"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1987.19"},{"key":"e_1_2_1_24_1","volume-title":"Proceedings of the 4th SODA. 500--504","author":"Matula D. W.","year":"1993","unstructured":"D. W. Matula . 1993 . A linear time 2 + &epsi; approximation algorithm for edge connectivity . In Proceedings of the 4th SODA. 500--504 . D. W. Matula. 1993. A linear time 2 + &epsi; approximation algorithm for edge connectivity. In Proceedings of the 4th SODA. 500--504."},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.4064\/fm-10-1-96-115"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1137\/0405004"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01758778"},{"key":"e_1_2_1_28_1","first-page":"136","article-title":"An algorithm for finding the edge connectity of graphs","volume":"2","author":"Podderyugin V. D.","year":"1973","unstructured":"V. D. Podderyugin . 1973 . An algorithm for finding the edge connectity of graphs . Vopr. Kibern. 2 (1973), 136 . V. D. Podderyugin. 1973. An algorithm for finding the edge connectity of graphs. Vopr. Kibern. 2 (1973), 136.","journal-title":"Vopr. Kibern."},{"key":"e_1_2_1_29_1","volume-title":"Combinatorial Optimization: Polyhedra and Efficiency","author":"Schrijver A.","year":"2003","unstructured":"A. Schrijver . 2003 . Combinatorial Optimization: Polyhedra and Efficiency . Springer , NY. A. Schrijver. 2003. Combinatorial Optimization: Polyhedra and Efficiency. Springer, NY."},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1137\/08074489X"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1145\/263867.263872"}],"container-title":["Journal of the ACM"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3274663","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3274663","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T00:57:56Z","timestamp":1750208276000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3274663"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018,12,12]]},"references-count":31,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2019,2,28]]}},"alternative-id":["10.1145\/3274663"],"URL":"https:\/\/doi.org\/10.1145\/3274663","relation":{},"ISSN":["0004-5411","1557-735X"],"issn-type":[{"value":"0004-5411","type":"print"},{"value":"1557-735X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2018,12,12]]},"assertion":[{"value":"2015-09-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2018-08-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2018-12-12","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}