{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,9,12]],"date-time":"2026-09-12T02:55:25Z","timestamp":1789181725570,"version":"build-2803163510"},"reference-count":40,"publisher":"Association for Computing Machinery (ACM)","license":[{"start":{"date-parts":[[2015,1,7]],"date-time":"2015-01-07T00:00:00Z","timestamp":1420588800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"CSCAPES Institute, a DOE project"},{"name":"DFG SA 933\/10-1"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["ACM J. Exp. Algorithmics"],"published-print":{"date-parts":[[2015,2,3]]},"abstract":"<jats:p>The graph partitioning problem is widely used and studied in many practical and theoretical applications. Today, multilevel strategies represent one of the most effective and efficient generic frameworks for solving this problem on large-scale graphs. Most of the attention in designing multilevel partitioning frameworks has been on the refinement phase. In this work, we focus on the coarsening phase, which is responsible for creating structures similar to the original but smaller graphs. We compare different matching- and AMG-based coarsening schemes, experiment with the algebraic distance between nodes, and demonstrate computational results on several classes of graphs that emphasize the running time and quality advantages of different coarsening schemes.<\/jats:p>","DOI":"10.1145\/2670338","type":"journal-article","created":{"date-parts":[[2015,1,12]],"date-time":"2015-01-12T20:02:10Z","timestamp":1421092930000},"page":"1-24","source":"Crossref","is-referenced-by-count":36,"title":["Advanced Coarsening Schemes for Graph Partitioning"],"prefix":"10.1145","volume":"19","author":[{"given":"Ilya","family":"Safro","sequence":"first","affiliation":[{"name":"Clemson University, Clemson SC, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Peter","family":"Sanders","sequence":"additional","affiliation":[{"name":"Karlsruhe Institute of Technology, Karlsruhe, Germany"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Christian","family":"Schulz","sequence":"additional","affiliation":[{"name":"Karlsruhe Institute of Technology, Karlsruhe, Germany"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2015,1,7]]},"reference":[{"key":"e_1_2_1_1_1","volume-title":"Retrieved","author":"Bader D. A.","year":"2014"},{"key":"e_1_2_1_2_1","volume-title":"Graph Drawing. Lecture Notes in Computer Science","volume":"6502","author":"Bartel G."},{"key":"e_1_2_1_3_1","volume-title":"Multiscale and Multiresolution Methods. Lecture Notes in Computational Science and Engineering","volume":"20","author":"Brandt A.","year":"2001"},{"key":"e_1_2_1_4_1","volume-title":"Multilevel Optimization in VLSICAD. Combinatorial Optimization","volume":"14","author":"Brandt A."},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(92)90140-Q"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1109\/12.508322"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1137\/090775087"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-11169-3_14"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/1081870.1081948"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0020-0190(02)00393-9"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10898-009-9520-1"},{"key":"e_1_2_1_12_1","volume-title":"Proceedings of the 19th Conference on Design Automation. 175--181","author":"Fiduccia C. M."},{"key":"e_1_2_1_13_1","first-page":"10","article-title":"Algorithms for graph partitioning: A survey","volume":"3","author":"Fjallstrom P. O.","year":"1998","journal-title":"Linkoping Electronic Articles in Computer and Information Science"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0895480199335829"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10107-011-0503-x"},{"key":"e_1_2_1_16_1","volume-title":"Scientific Computing: An Introductory Survey","author":"Heath M. T.","year":"2002"},{"key":"e_1_2_1_17_1","volume-title":"Proceedings of the 24th IEEE International Symposium on Parallel and Distributed Processing. 1--10","author":"Holtgrewe M."},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1137\/S1064827500377733"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1287\/ijoc.12.3.177.12637"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/224170.224229"},{"key":"e_1_2_1_21_1","volume-title":"Retrieved","author":"Lescovec J.","year":"2014"},{"key":"e_1_2_1_22_1","volume-title":"Experimental Algorithms. Lecture Notes in Computer Science","volume":"4525","author":"Maue J."},{"key":"e_1_2_1_23_1","volume-title":"Proceedings of the IEEE International Symposium on Parallel and Distributed Processing (IPDPS\u201908)","author":"Meyerhenke H."},{"key":"e_1_2_1_24_1","volume-title":"Retrieved","author":"Pellegrini F.","year":"2014"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1137\/0611030"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1137\/100791142"},{"key":"e_1_2_1_27_1","volume-title":"Technical Report MCS05-01. Department of Computer Science and Applied Mathematics","author":"Ron D.","year":"2005"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jalgor.2004.10.004"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1145\/1412228.1412232"},{"key":"e_1_2_1_30_1","volume-title":"Benchmark with Potentially Hard Graphs for Partitioning Problem. Retrieved","author":"Safro I.","year":"2014"},{"key":"e_1_2_1_31_1","volume-title":"Lecture Notes in Computer Science","volume":"6942","author":"Sanders P."},{"key":"e_1_2_1_32_1","volume-title":"Proceedings of the 12th Workshop on Algorithm Engineering and Experimentation (ALENEX\u201912)","author":"Sanders P."},{"key":"e_1_2_1_33_1","unstructured":"K. Schloegel G. Karypis V. Kumar J. Dongarra I. Foster G. Fox K. Kennedy and A. White. 2000. Graph Partitioning for High Performance Scientific Simulations. Morgan Kaufmann.  K. Schloegel G. Karypis V. Kumar J. Dongarra I. Foster G. Fox K. Kennedy and A. White. 2000. Graph Partitioning for High Performance Scientific Simulations. Morgan Kaufmann."},{"key":"e_1_2_1_34_1","volume-title":"Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition. 70--77","author":"Sharon E."},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1023\/B:JOGO.0000042115.44455.f3"},{"key":"e_1_2_1_36_1","unstructured":"L. E. Stock. 2006. Strategic Logistics Management. Lightning Source La Vergne TN. http:\/\/books.google.com\/books&quest;id=1LyCAQAACAAJ.  L. E. Stock. 2006. Strategic Logistics Management. Lightning Source La Vergne TN. http:\/\/books.google.com\/books&quest;id=1LyCAQAACAAJ."},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1145\/1401890.1401972"},{"key":"e_1_2_1_38_1","unstructured":"U. Trottenberg and A. Schuller. 2001. Multigrid. Academic Press Orlando FL.   U. Trottenberg and A. Schuller. 2001. Multigrid. Academic Press Orlando FL."},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1023\/B:ANOR.0000039525.80601.15"},{"key":"e_1_2_1_40_1","volume-title":"JOSTLE: Parallel multilevel graph-partitioning software\u2014an overview","author":"Walshaw C.","year":"2007"}],"container-title":["ACM Journal of Experimental Algorithmics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2670338","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2670338","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T07:19:20Z","timestamp":1750231160000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2670338"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015,1,7]]},"references-count":40,"alternative-id":["10.1145\/2670338"],"URL":"https:\/\/doi.org\/10.1145\/2670338","relation":{},"ISSN":["1084-6654","1084-6654"],"issn-type":[{"value":"1084-6654","type":"print"},{"value":"1084-6654","type":"electronic"}],"subject":[],"published":{"date-parts":[[2015,1,7]]}}}