{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,19]],"date-time":"2026-02-19T02:30:55Z","timestamp":1771468255959,"version":"3.50.1"},"publisher-location":"Cham","reference-count":27,"publisher":"Springer Nature Switzerland","isbn-type":[{"value":"9783031396977","type":"print"},{"value":"9783031396984","type":"electronic"}],"license":[{"start":{"date-parts":[[2023,1,1]],"date-time":"2023-01-01T00:00:00Z","timestamp":1672531200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2023,8,24]],"date-time":"2023-08-24T00:00:00Z","timestamp":1692835200000},"content-version":"vor","delay-in-days":235,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2023]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>We describe the engineering of the distributed-memory multilevel graph partitioner . It scales to (at least) 8192 cores while achieving partitioning quality comparable to widely used sequential and shared-memory graph partitioners. In comparison, previous distributed graph partitioners scale only in more restricted scenarios and often induce a considerable quality penalty compared to non-distributed partitioners. When partitioning into a large number of blocks, they even produce infeasible solution that violate the balancing constraint.  achieves its robustness by a scalable distributed implementation of the deep-multilevel scheme for graph partitioning. Crucially, this includes new algorithms for balancing during refinement <jats:italic>and<\/jats:italic> coarsening.<\/jats:p>","DOI":"10.1007\/978-3-031-39698-4_30","type":"book-chapter","created":{"date-parts":[[2023,8,23]],"date-time":"2023-08-23T06:02:40Z","timestamp":1692770560000},"page":"443-457","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":8,"title":["Distributed Deep Multilevel Graph Partitioning"],"prefix":"10.1007","author":[{"given":"Peter","family":"Sanders","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Daniel","family":"Seemaier","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2023,8,24]]},"reference":[{"issue":"11","key":"30_CR1","doi-asserted-by":"publisher","first-page":"2710","DOI":"10.1109\/TPDS.2020.3001645","volume":"31","author":"Y Akhremtsev","year":"2020","unstructured":"Akhremtsev, Y., Sanders, P., Schulz, C.: High-quality shared-memory graph partitioning. IEEE Trans. Parallel Distrib. Syst. 31(11), 2710\u20132722 (2020)","journal-title":"IEEE Trans. Parallel Distrib. Syst."},{"key":"30_CR2","volume-title":"Graph Partitioning","year":"2011","unstructured":"Bichot, C., Siarry, P. (eds.): Graph Partitioning. Wiley, Hoboken (2011)"},{"key":"30_CR3","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"117","DOI":"10.1007\/978-3-319-49487-6_4","volume-title":"Algorithm Engineering","author":"A Bulu\u00e7","year":"2016","unstructured":"Bulu\u00e7, A., Meyerhenke, H., Safro, I., Sanders, P., Schulz, C.: Recent advances in graph partitioning. In: Kliemann, L., Sanders, P. (eds.) Algorithm Engineering. LNCS, vol. 9220, pp. 117\u2013158. Springer, Cham (2016). https:\/\/doi.org\/10.1007\/978-3-319-49487-6_4"},{"key":"30_CR4","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/3571808","volume":"55","author":"UV \u00c7ataly\u00fcrek","year":"2022","unstructured":"\u00c7ataly\u00fcrek, U.V., et al.: More recent advances in (hyper)graph partitioning. ACM Comput. Surv. 55, 1\u201338 (2022)","journal-title":"ACM Comput. Surv."},{"issue":"6\u20138","key":"30_CR5","doi-asserted-by":"publisher","first-page":"318","DOI":"10.1016\/j.parco.2007.12.001","volume":"34","author":"C Chevalier","year":"2008","unstructured":"Chevalier, C., Pellegrini, F.: PT-scotch: a tool for efficient parallel graph ordering. Parallel Comput. 34(6\u20138), 318\u2013331 (2008)","journal-title":"Parallel Comput."},{"key":"30_CR6","doi-asserted-by":"crossref","unstructured":"Devine, K.D., et al.: Parallel hypergraph partitioning for scientific computing. In: 20th International Parallel and Distributed Processing Symposium (IPDPS 2006) (2006)","DOI":"10.1109\/IPDPS.2006.1639359"},{"issue":"2","key":"30_CR7","doi-asserted-by":"publisher","first-page":"201","DOI":"10.1007\/s101070100263","volume":"91","author":"ED Dolan","year":"2002","unstructured":"Dolan, E.D., Mor\u00e9, J.J.: Benchmarking optimization software with performance profiles. Math. Program. 91(2), 201\u2013213 (2002)","journal-title":"Math. Program."},{"key":"30_CR8","doi-asserted-by":"publisher","first-page":"200","DOI":"10.1016\/j.jpdc.2019.03.011","volume":"131","author":"D Funke","year":"2019","unstructured":"Funke, D., et al.: Communication-free massively distributed graph generation. J. Parallel Distrib. Comput. 131, 200\u2013217 (2019)","journal-title":"J. Parallel Distrib. Comput."},{"key":"30_CR9","unstructured":"Gottesb\u00fcren, L., et al.: Deep multilevel graph partitioning. In: 29th European Symposium on Algorithms (ESA). LIPIcs, vol. 204, pp. 48:1\u201348:17. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik (2021)"},{"key":"30_CR10","unstructured":"Gottesb\u00fcren, L., Heuer, T., Sanders, P.: Parallel flow-based hypergraph partitioning. In: 20th International Symposium on Experimental Algorithms (SEA 2022), vol. 233, pp. 5:1\u20135:21. LIPICS (2022)"},{"key":"30_CR11","doi-asserted-by":"crossref","unstructured":"Gottesb\u00fcren, L., Heuer, T., Sanders, P., Schlag, S.: Scalable shared-memory hypergraph partitioning. In: 23rd Workshop on Algorithm Engineering and Experiments (ALENEX 2021), pp. 16\u201330. SIAM (2021)","DOI":"10.1137\/1.9781611976472.2"},{"issue":"1","key":"30_CR12","doi-asserted-by":"publisher","first-page":"359","DOI":"10.1137\/S1064827595287997","volume":"20","author":"G Karypis","year":"1998","unstructured":"Karypis, G., Kumar, V.: A fast and high quality multilevel scheme for partitioning irregular graphs. SIAM J. Sci. Comput. 20(1), 359\u2013392 (1998)","journal-title":"SIAM J. Sci. Comput."},{"issue":"1","key":"30_CR13","doi-asserted-by":"publisher","first-page":"96","DOI":"10.1006\/jpdc.1997.1404","volume":"48","author":"G Karypis","year":"1998","unstructured":"Karypis, G., Kumar, V.: Multilevel $$k$$-way partitioning scheme for irregular graphs. J. Parallel Distrib. Comput. 48(1), 96\u2013129 (1998)","journal-title":"J. Parallel Distrib. Comput."},{"key":"30_CR14","doi-asserted-by":"crossref","unstructured":"LaSalle, D., Karypis, G.: Multi-threaded graph partitioning. In: 27th IEEE International Parallel and Distributed Processing Symposium (IPDPS), pp. 225\u2013236 (2013)","DOI":"10.1109\/IPDPS.2013.50"},{"key":"30_CR15","doi-asserted-by":"crossref","unstructured":"LaSalle, D., et al.: Improving graph partitioning for modern graphs and architectures. In: 5th Workshop on Irregular Applications - Architectures and Algorithms (IA3), pp. 14:1\u201314:4. ACM (2015)","DOI":"10.1145\/2833179.2833188"},{"key":"30_CR16","doi-asserted-by":"crossref","unstructured":"von Looz, M., Tzovas, C., Meyerhenke, H.: Balanced k-means for parallel geometric partitioning. In: 47th International Conference on Parallel Processing (ICPP), pp. 52:1\u201352:10. ACM (2018)","DOI":"10.1145\/3225058.3225148"},{"key":"30_CR17","doi-asserted-by":"crossref","unstructured":"Maier, T., Sanders, P., Dementiev, R.: Concurrent hash tables: fast and general(?)! ACM Trans. Parallel Comput. 5(4), 16:1\u201316:32 (2019)","DOI":"10.1145\/3309206"},{"key":"30_CR18","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"351","DOI":"10.1007\/978-3-319-07959-2_30","volume-title":"Experimental Algorithms","author":"H Meyerhenke","year":"2014","unstructured":"Meyerhenke, H., Sanders, P., Schulz, C.: Partitioning complex networks via size-constrained clustering. In: Gudmundsson, J., Katajainen, J. (eds.) SEA 2014. LNCS, vol. 8504, pp. 351\u2013363. Springer, Cham (2014). https:\/\/doi.org\/10.1007\/978-3-319-07959-2_30"},{"issue":"9","key":"30_CR19","doi-asserted-by":"publisher","first-page":"2625","DOI":"10.1109\/TPDS.2017.2671868","volume":"28","author":"H Meyerhenke","year":"2017","unstructured":"Meyerhenke, H., Sanders, P., Schulz, C.: Parallel graph partitioning for complex networks. IEEE Trans. Parallel Distrib. Syst. 28(9), 2625\u20132638 (2017)","journal-title":"IEEE Trans. Parallel Distrib. Syst."},{"key":"30_CR20","doi-asserted-by":"publisher","first-page":"36","DOI":"10.1103\/PhysRevE.76.036106","volume":"76","author":"N Raghavan","year":"2007","unstructured":"Raghavan, N., Albert, R., Kumara, S.: Near linear time algorithm to detect community structures in large-scale networks. Phys. Rev. E Stat. Nonlinear Soft Matter Phys. 76, 36\u2013106 (2007)","journal-title":"Phys. Rev. E Stat. Nonlinear Soft Matter Phys."},{"key":"30_CR21","doi-asserted-by":"crossref","unstructured":"Sanders, P., Schimek, M.: Engineering massively parallel MST algorithms. In: 27th IEEE International Parallel and Distributed Processing Symposium (IPDPS) (2023)","DOI":"10.1109\/IPDPS54959.2023.00075"},{"key":"30_CR22","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"164","DOI":"10.1007\/978-3-642-38527-8_16","volume-title":"Experimental Algorithms","author":"P Sanders","year":"2013","unstructured":"Sanders, P., Schulz, C.: Think locally, act globally: highly balanced graph partitioning. In: Bonifaci, V., Demetrescu, C., Marchetti-Spaccamela, A. (eds.) SEA 2013. LNCS, vol. 7933, pp. 164\u2013175. Springer, Heidelberg (2013). https:\/\/doi.org\/10.1007\/978-3-642-38527-8_16"},{"key":"30_CR23","unstructured":"Sanders, P., Seemaier, D.: Distributed deep multilevel graph partitioning (2023). https:\/\/arxiv.org\/abs\/2303.01417"},{"key":"30_CR24","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/978-3-319-63962-8_312-2","volume-title":"Encyclopedia of Big Data Technologies","author":"C Schulz","year":"2018","unstructured":"Schulz, C., Strash, D.: Graph partitioning: formulations and applications to big data. In: Sakr, S., Zomaya, A. (eds.) Encyclopedia of Big Data Technologies, pp. 1\u20137. Springer, Cham (2018). https:\/\/doi.org\/10.1007\/978-3-319-63962-8_312-2"},{"issue":"12","key":"30_CR25","doi-asserted-by":"publisher","first-page":"2789","DOI":"10.1109\/TPDS.2020.3002150","volume":"31","author":"GM Slota","year":"2020","unstructured":"Slota, G.M., et al.: Scalable, multi-constraint, complex-objective graph partitioning. IEEE Trans. Parallel Distrib. Syst. 31(12), 2789\u20132801 (2020)","journal-title":"IEEE Trans. Parallel Distrib. Syst."},{"key":"30_CR26","doi-asserted-by":"crossref","unstructured":"Slota, G.M., Madduri, K., Rajamanickam, S.: PuLP: scalable multi-objective multi-constraint partitioning for small-world networks. In: 2014 IEEE International Conference on Big Data (IEEE BigData 2014), pp. 481\u2013490 (2014)","DOI":"10.1109\/BigData.2014.7004265"},{"key":"30_CR27","first-page":"27","volume":"10","author":"C Walshaw","year":"2007","unstructured":"Walshaw, C., Cross, M.: JOSTLE: parallel multilevel graph-partitioning software \u2013 an overview. Mesh Partitioning Tech. Domain Decomposition Tech. 10, 27\u201358 (2007)","journal-title":"Mesh Partitioning Tech. Domain Decomposition Tech."}],"container-title":["Lecture Notes in Computer Science","Euro-Par 2023: Parallel Processing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-031-39698-4_30","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,8,23]],"date-time":"2023-08-23T06:03:14Z","timestamp":1692770594000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-031-39698-4_30"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023]]},"ISBN":["9783031396977","9783031396984"],"references-count":27,"URL":"https:\/\/doi.org\/10.1007\/978-3-031-39698-4_30","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2023]]},"assertion":[{"value":"24 August 2023","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"Euro-Par","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"European Conference on Parallel Processing","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Limassol","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Cyprus","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2023","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"28 August 2023","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"1 September 2023","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"europar2023","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"https:\/\/2023.euro-par.org\/","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Single-blind","order":1,"name":"type","label":"Type","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"easychair","order":2,"name":"conference_management_system","label":"Conference Management System","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"164","order":3,"name":"number_of_submissions_sent_for_review","label":"Number of Submissions Sent for Review","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"49","order":4,"name":"number_of_full_papers_accepted","label":"Number of Full Papers Accepted","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"0","order":5,"name":"number_of_short_papers_accepted","label":"Number of Short Papers Accepted","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"30% - The value is computed by the equation \"Number of Full Papers Accepted \/ Number of Submissions Sent for Review * 100\" and then rounded to a whole number.","order":6,"name":"acceptance_rate_of_full_papers","label":"Acceptance Rate of Full Papers","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"3.98","order":7,"name":"average_number_of_reviews_per_paper","label":"Average Number of Reviews per Paper","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"4","order":8,"name":"average_number_of_papers_per_reviewer","label":"Average Number of Papers per Reviewer","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"Yes","order":9,"name":"external_reviewers_involved","label":"External Reviewers Involved","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}}]}}