{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,7,20]],"date-time":"2024-07-20T06:00:51Z","timestamp":1721455251196},"reference-count":138,"publisher":"Association for Computing Machinery (ACM)","funder":[{"name":"DFG","award":["WA654\/19-2, SA933\/10-2, SA933\/11-1, and SCHU 2567\/1-2"]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["ACM J. Exp. Algorithmics"],"published-print":{"date-parts":[[2022,12,31]]},"abstract":"\n Hypergraphs are a generalization of graphs where edges (aka\n nets<\/jats:italic>\n ) are allowed to connect more than two vertices. They have a similarly wide range of applications as graphs. This article considers the fundamental and intensively studied problem of\n balanced hypergraph partitioning (BHP)<\/jats:italic>\n , which asks for partitioning the vertices into\n k<\/jats:italic>\n disjoint blocks of bounded size while minimizing an objective function over the hyperedges. Here, we consider the two most commonly used objectives: the\n cut-net metric<\/jats:italic>\n and the\n connectivity metric<\/jats:italic>\n .\n <\/jats:p>\n \n We describe our open-source hypergraph partitioner\n KaHyPar<\/jats:italic>\n which is based on the successful multi-level approach\u2014driving it to the extreme of using one level for (almost) every vertex. Using carefully designed data structures and dynamic update techniques, this approach turns out to have a very good time\u2013quality tradeoff. We present two preprocessing techniques\u2014\n pin sparsification using locality-sensitive hashing (LSH)<\/jats:italic>\n and\n community detection based on the Louvain algorithm<\/jats:italic>\n . The community structure is used to guide the\n coarsening process<\/jats:italic>\n that incrementally contracts vertices.\n Portfolio-based partitioning<\/jats:italic>\n of the contracted hypergraph then already achieves a good initial solution. While reversing the contraction process, a combination of several refinement techniques achieves a good final partitioning. In particular, we support a\n highly-localized local search<\/jats:italic>\n that can directly produce a\n k<\/jats:italic>\n -way partitioning and complement this with\n flow-based techniques<\/jats:italic>\n that take a more global view. Optionally, a\n memetic algorithm<\/jats:italic>\n evolves a pool of solution candidates to an overall good solution.\n <\/jats:p>\n We evaluate KaHyPar for a large set of instances from a wide range of application domains. With respect to quality, KaHyPar outperforms all previously considered systems that can handle large hypergraphs such as hMETIS, PaToH, Mondriaan, or Zoltan. Somewhat surprisingly, to some extend, this even extends to graph partitioners such as KaHIP when considering the special case of graphs. KaHyPar is also faster than most of these systems except for PaToH which represents a different speed\u2013quality tradeoff.<\/jats:p>","DOI":"10.1145\/3529090","type":"journal-article","created":{"date-parts":[[2022,4,21]],"date-time":"2022-04-21T12:48:10Z","timestamp":1650545290000},"page":"1-39","source":"Crossref","is-referenced-by-count":20,"title":["High-Quality Hypergraph Partitioning"],"prefix":"10.1145","volume":"27","author":[{"ORCID":"http:\/\/orcid.org\/0000-0003-1550-882X","authenticated-orcid":false,"given":"Sebastian","family":"Schlag","sequence":"first","affiliation":[{"name":"Karlsruhe Institute of Technology, Postfach, Karlsruhe, Germany"}]},{"ORCID":"http:\/\/orcid.org\/0000-0003-1635-8747","authenticated-orcid":false,"given":"Tobias","family":"Heuer","sequence":"additional","affiliation":[{"name":"Karlsruhe Institute of Technology"}]},{"ORCID":"http:\/\/orcid.org\/0000-0003-1895-5828","authenticated-orcid":false,"given":"Lars","family":"Gottesb\u00fcren","sequence":"additional","affiliation":[{"name":"Karlsruhe Institute of Technology"}]},{"ORCID":"http:\/\/orcid.org\/0000-0002-3195-6326","authenticated-orcid":false,"given":"Yaroslav","family":"Akhremtsev","sequence":"additional","affiliation":[{"name":"Karlsruhe Institute of Technology"}]},{"ORCID":"http:\/\/orcid.org\/0000-0002-2823-3506","authenticated-orcid":false,"given":"Christian","family":"Schulz","sequence":"additional","affiliation":[{"name":"Heidelberg University, Heidelberg, Germany"}]},{"ORCID":"http:\/\/orcid.org\/0000-0003-3330-9349","authenticated-orcid":false,"given":"Peter","family":"Sanders","sequence":"additional","affiliation":[{"name":"Karlsruhe Institute of Technology"}]}],"member":"320","published-online":{"date-parts":[[2023,2,10]]},"reference":[{"key":"e_1_3_4_2_2","volume-title":"Parallel and External High Quality Graph Partitioning","author":"Akhremtsev Y.","year":"2019","unstructured":"Y. Akhremtsev. 2019. Parallel and External High Quality Graph Partitioning. Ph.D. Dissertation. Karlsruhe Institute of Technology."},{"key":"e_1_3_4_3_2","first-page":"28","volume-title":"Proceedings of the 19th Workshop on Algorithm Engineering and Experiments","author":"Akhremtsev Y.","year":"2017","unstructured":"Y. Akhremtsev, T. Heuer, P. Sanders, and S. Schlag. 2017. Engineering a direct k-way hypergraph partitioning algorithm. In Proceedings of the 19th Workshop on Algorithm Engineering and Experiments. SIAM, 28\u201342."},{"key":"e_1_3_4_4_2","doi-asserted-by":"publisher","DOI":"10.1109\/TPDS.2020.3001645"},{"key":"e_1_3_4_5_2","first-page":"80","volume-title":"Proceedings of the International Symposium on Physical Design","author":"Alpert C. J.","year":"1998","unstructured":"C. J. Alpert. 1998. The ISPD98 circuit benchmark suite. In Proceedings of the International Symposium on Physical Design. 80\u201385."},{"key":"e_1_3_4_6_2","doi-asserted-by":"publisher","DOI":"10.1109\/43.712098"},{"key":"e_1_3_4_7_2","doi-asserted-by":"publisher","DOI":"10.1016\/0167-9260(95)00008-4"},{"key":"e_1_3_4_8_2","doi-asserted-by":"publisher","DOI":"10.1145\/1327452.1327494"},{"key":"e_1_3_4_9_2","volume-title":"Evolutionary Hypergraph Partitioning","author":"Andre R.","year":"2017","unstructured":"R. Andre. 2017. Evolutionary Hypergraph Partitioning. Bachelor Thesis. Karlsruhe Institute of Technology."},{"key":"e_1_3_4_10_2","doi-asserted-by":"crossref","first-page":"347","DOI":"10.1145\/3205455.3205475","volume-title":"Proceedings of the Genetic and Evolutionary Computation Conference.","author":"Andre R.","year":"2018","unstructured":"R. Andre, S. Schlag, and C. Schulz. 2018. Memetic multilevel hypergraph partitioning. In Proceedings of the Genetic and Evolutionary Computation Conference.ACM, 347\u2013354."},{"key":"e_1_3_4_11_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.jpdc.2007.09.006"},{"key":"e_1_3_4_12_2","series-title":"Contemporary Mathematics","doi-asserted-by":"crossref","DOI":"10.1090\/conm\/588","volume-title":"Graph Partitioning and Graph Clustering, 10th DIMACS Implementation Challenge Workshop","author":"Bader D. A.","year":"2013","unstructured":"D. A. Bader, H. Meyerhenke, P. Sanders, and D. Wagner (Eds.). 2013. Graph Partitioning and Graph Clustering, 10th DIMACS Implementation Challenge Workshop. Contemporary Mathematics, Vol. 588. American Mathematical Society."},{"key":"e_1_3_4_13_2","unstructured":"A. Belov D. Diepold M. Heule and M. J\u00e4rvisalo. 2014. The SAT Competition 2014. Retrieved from http:\/\/www.satcompetition.org\/2014\/."},{"key":"e_1_3_4_14_2","doi-asserted-by":"crossref","first-page":"205","DOI":"10.1007\/978-94-010-1826-5_10","volume-title":"Proceedings of the Combinatorics","volume":"16","author":"Berge C.","year":"1975","unstructured":"C. Berge. 1975. Isomorphism problems for hypergraphs. In Proceedings of the Combinatorics. M. Hall Jr. and J. H. van Lint (Eds.), Vol. 16. Springer, 205\u2013214."},{"key":"e_1_3_4_15_2","doi-asserted-by":"publisher","DOI":"10.5555\/1096893"},{"key":"e_1_3_4_16_2","volume-title":"Graph Partitioning","author":"Bichot C.","year":"2011","unstructured":"C. Bichot and P. Siarry (Eds.). 2011. Graph Partitioning. Wiley."},{"key":"e_1_3_4_17_2","volume-title":"Mondriaan for Sparse Matrix Partitioning","author":"Bisseling R.","year":"2019","unstructured":"R. Bisseling, B. F. Auer, T. van Leeuwen, W. Meesen, M. van Oort, D. Pelt, B. Vastenhouw, and A.-J. Yzelman. 2019. Mondriaan for Sparse Matrix Partitioning. Retrieved from https:\/\/www.staff.science.uu.nl\/bisse101\/Mondriaan\/."},{"key":"e_1_3_4_18_2","doi-asserted-by":"crossref","first-page":"321","DOI":"10.1201\/b11644-13","article-title":"Two-dimensional approaches to sparse matrix partitioning","author":"Bisseling R. H.","year":"2012","unstructured":"R. H. Bisseling, B. O. A. Fagginger, A. N. Yzelman, T. van Leeuwen, and \u00dc. V. \u00c7ataly\u00fcrek. 2012. Two-dimensional approaches to sparse matrix partitioning. Combinatorial Scientific Computing (2012), 321\u2013349.","journal-title":"Combinatorial Scientific Computing"},{"key":"e_1_3_4_19_2","doi-asserted-by":"publisher","DOI":"10.1162\/evco.1996.4.4.361"},{"key":"e_1_3_4_20_2","doi-asserted-by":"publisher","DOI":"10.1088\/1742-5468\/2008\/10\/P10008"},{"key":"e_1_3_4_21_2","unstructured":"E. Boman K. Devine V. Leung S. Rajamanickam L. A. Riesen and \u00dc. V. \u00c7ataly\u00fcrek. 2012. Zoltan User\u2019s Guide. Retrieved from http:\/\/www.cs.sandia.gov\/Zoltan\/ug_html\/ug_alg_patoh.html."},{"key":"e_1_3_4_22_2","first-page":"1456","volume-title":"Proceedings of the 20th International Conference on Knowledge Discovery and Data Mining","author":"Bourse F.","year":"2014","unstructured":"F. Bourse, M. Lelarge, and M. Vojnovic. 2014. Balanced graph edge partition. In Proceedings of the 20th International Conference on Knowledge Discovery and Data Mining. ACM, 1456\u20131465."},{"key":"e_1_3_4_23_2","doi-asserted-by":"publisher","DOI":"10.1109\/tkde.2007.190689"},{"key":"e_1_3_4_24_2","doi-asserted-by":"publisher","DOI":"10.1145\/176454.176484"},{"key":"e_1_3_4_25_2","volume-title":"Proceedings of the Compression and Complexity of Sequences","author":"Broder A. Z.","year":"1997","unstructured":"A. Z. Broder. 1997. On the resemblance and containment of documents. In Proceedings of the Compression and Complexity of Sequences. IEEE."},{"key":"e_1_3_4_26_2","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.1999.1690"},{"key":"e_1_3_4_27_2","doi-asserted-by":"publisher","DOI":"10.1016\/S0169-7552(97)00031-7"},{"key":"e_1_3_4_28_2","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(92)90140-Q"},{"key":"e_1_3_4_29_2","series-title":"Proceedings of the Algorithm Engineering","first-page":"117","volume":"9220","author":"Buluc A.","year":"2016","unstructured":"A. Buluc, H. Meyerhenke, I. Safro, P. Sanders, and C. Schulz. 2016. Recent advances in graph partitioning. In Proceedings of the Algorithm Engineering. Lasse Kliemann and Peter Sanders (Eds.), Lecture Notes in Computer Science, Vol. 9220. Springer, 117\u2013158."},{"key":"e_1_3_4_30_2","first-page":"661","volume-title":"Proceedings of the Asia South Pacific Design Automation Conference.","author":"Caldwell A. E.","year":"2000","unstructured":"A. E. Caldwell, A. B. Kahng, and I. L. Markov. 2000. Improved algorithms for hypergraph bipartitioning. In Proceedings of the Asia South Pacific Design Automation Conference.661\u2013666."},{"key":"e_1_3_4_31_2","volume-title":"Statistics at Square One","author":"Campbell M. J.","year":"2009","unstructured":"M. J. Campbell and T. D. Swinscow. 2009. Statistics at Square One. BMJ Publishing Group."},{"key":"e_1_3_4_32_2","unstructured":"\u00dc. V. \u00c7ataly\u00fcrek. [n.d.]. ISPD98 Benchmark. Retrieved from http:\/\/bmi.osu.edu\/umit\/PaToH\/ispd98.html."},{"key":"e_1_3_4_33_2","volume-title":"PaToH (Partitioning Tools for Hypergraph)","author":"\u00c7ataly\u00fcrek \u00dc. V.","year":"2019","unstructured":"\u00dc. V. \u00c7ataly\u00fcrek. 2019. PaToH (Partitioning Tools for Hypergraph). Retrieved from https:\/\/www.cc.gatech.edu\/umit\/software.html."},{"key":"e_1_3_4_34_2","doi-asserted-by":"publisher","DOI":"10.1109\/71.780863"},{"key":"e_1_3_4_35_2","unstructured":"\u00dc. V. \u00c7ataly\u00fcrek and C. Aykanat. 2011. PaToH: Partitioning Tool for Hypergraphs. Retrieved from https:\/\/www.cc.gatech.edu\/umit\/PaToH\/manual.pdf."},{"key":"e_1_3_4_36_2","first-page":"53","volume-title":"Proceedings of the Graph Partitioning and Graph Clustering, 10th DIMACS Implementation Challenge Workshop","author":"\u00c7ataly\u00fcrek \u00dc. V.","year":"2012","unstructured":"\u00dc. V. \u00c7ataly\u00fcrek, M. Deveci, K. Kaya, and B. U\u00e7ar. 2012. UMPa: A multi-objective, multi-level partitioner for communication minimization. In Proceedings of the Graph Partitioning and Graph Clustering, 10th DIMACS Implementation Challenge Workshop. 53\u201366."},{"key":"e_1_3_4_37_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.jpdc.2014.12.002"},{"key":"e_1_3_4_38_2","volume-title":"Hybrid Spectral\/Iterative Partitioning","author":"Chan P. K.","year":"1997","unstructured":"P. K. Chan, M. D. F. Schlag, and J. Y. Zien. 1997. Hybrid Spectral\/Iterative Partitioning. Technical Report UCUC-CRL-97\u201309. University of California at Santa Cruz."},{"key":"e_1_3_4_39_2","first-page":"436","volume-title":"Proceedings of the International Conference on Computer-Aided Design","author":"Chan P. K.","year":"1997","unstructured":"P. K. Chan, M. D. F. Schlag, and J. Y. Zien. 1997. Hybrid spectral\/iterative partitioning. In Proceedings of the International Conference on Computer-Aided Design. IEEE, 436\u2013440."},{"key":"e_1_3_4_40_2","first-page":"380","volume-title":"Proceedings of the 34th ACM Symposium on Theory of Computing","author":"Charikar M.","year":"2002","unstructured":"M. Charikar. 2002. Similarity estimation techniques from rounding algorithms. In Proceedings of the 34th ACM Symposium on Theory of Computing. ACM, 380\u2013388."},{"key":"e_1_3_4_41_2","first-page":"512","volume-title":"Proceedings of the International Conference on Computer-Aided Design","author":"Cong J.","year":"1998","unstructured":"J. Cong and S. K. Lim. 1998. Multiway partitioning with pairwise movement. In Proceedings of the International Conference on Computer-Aided Design. 512\u2013516."},{"key":"e_1_3_4_42_2","first-page":"88","volume-title":"Proceedings of the International Symposium on Physical Design","author":"Cong J.","year":"2003","unstructured":"J. Cong, M. Romesis, and M. Xie. 2003. Optimality, scalability and stability study of partitioning and placement algorithms. In Proceedings of the International Symposium on Physical Design. 88\u201394."},{"key":"e_1_3_4_43_2","doi-asserted-by":"publisher","DOI":"10.14778\/1920841.1920853"},{"key":"e_1_3_4_44_2","doi-asserted-by":"publisher","DOI":"10.1145\/2049662.2049663"},{"key":"e_1_3_4_45_2","volume-title":"Evolutionary Computation - A Unified Approach","author":"Jong K. A. De","year":"2006","unstructured":"K. A. De Jong. 2006. Evolutionary Computation - A Unified Approach. MIT Press."},{"key":"e_1_3_4_46_2","first-page":"8:1\u20138:14","volume-title":"Proceedings of the 17th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems.","volume":"59","author":"Delling D.","year":"2017","unstructured":"D. Delling, J. Dibbelt, T. Pajor, and T. Z\u00fcndorf. 2017. Faster transit routing by hyper partitioning. In Proceedings of the 17th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems.G. D\u2019Angelo and T. Dollevoet (Eds.), Vol. 59. Schloss Dagstuhl \u2013 Leibniz-Zentrum fuer Informatik, 8:1\u20138:14."},{"key":"e_1_3_4_47_2","first-page":"1135","volume-title":"Proceedings of the 25th International Parallel and Distributed Processing Symposium","author":"Delling D.","year":"2011","unstructured":"D. Delling, A. V. Goldberg, I. Razenshteyn, and R. F. Werneck. 2011. Graph partitioning with natural cuts. In Proceedings of the 25th International Parallel and Distributed Processing Symposium. 1135\u20131146."},{"key":"e_1_3_4_48_2","volume-title":"Proceedings of the 20th International Parallel and Distributed Processing Symposium.","author":"Devine K. D.","year":"2006","unstructured":"K. D. Devine, E. G. Boman, R. T. Heaphy, R. H. Bisseling, and \u00dc. V. \u00c7ataly\u00fcrek. 2006. Parallel hypergraph partitioning for scientific computing. In Proceedings of the 20th International Parallel and Distributed Processing Symposium."},{"key":"e_1_3_4_49_2","first-page":"1277","article-title":"Algorithm for solution of a problem of maximum flow in networks with power estimation","volume":"11","author":"Dinic E. A.","year":"1970","unstructured":"E. A. Dinic. 1970. Algorithm for solution of a problem of maximum flow in networks with power estimation. Soviet Mathematics Doklady 11 (1970), 1277\u20131280.","journal-title":"Soviet Mathematics Doklady"},{"key":"e_1_3_4_50_2","doi-asserted-by":"publisher","DOI":"10.1007\/s101070100263"},{"key":"e_1_3_4_51_2","first-page":"65","article-title":"Logic partitioning","author":"Donath W. E.","year":"1988","unstructured":"W. E. Donath. 1988. Logic partitioning. Physical Design Automation of VLSI Systems (1988), 65\u201386.","journal-title":"Physical Design Automation of VLSI Systems"},{"key":"e_1_3_4_52_2","doi-asserted-by":"publisher","DOI":"10.5555\/800263.809204"},{"key":"e_1_3_4_53_2","doi-asserted-by":"publisher","DOI":"10.4153\/CJM-1956-045-5"},{"key":"e_1_3_4_54_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.physrep.2009.11.002"},{"key":"e_1_3_4_55_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.physrep.2016.09.002"},{"key":"e_1_3_4_56_2","first-page":"336","volume-title":"Proceedings of the 32nd International Parallel and Distributed Processing Symposium","author":"Funke D.","year":"2018","unstructured":"D. Funke, S. Lamm, P. Sanders, C. Schulz, D. Strash, and M. von Looz. 2018. Communication-free massively distributed graph generation. In Proceedings of the 32nd International Parallel and Distributed Processing Symposium. 336\u2013347."},{"key":"e_1_3_4_57_2","doi-asserted-by":"publisher","DOI":"10.5555\/578296"},{"key":"e_1_3_4_58_2","doi-asserted-by":"publisher","DOI":"10.5555\/645925.671516"},{"key":"e_1_3_4_59_2","first-page":"136","volume-title":"Proceedings of the 18th ACM Symposium on Theory of Computing","author":"Goldberg A. V.","year":"1986","unstructured":"A. V. Goldberg and R. E. Tarjan. 1986. A new approach to the maximum flow problem. In Proceedings of the 18th ACM Symposium on Theory of Computing. ACM, 136\u2013146."},{"key":"e_1_3_4_60_2","first-page":"17","volume-title":"Proceedings of the 10th USENIX Symposium on Operating Systems Design and Implementation.","author":"Gonzalez J. E.","year":"2012","unstructured":"J. E. Gonzalez, Y. Low, H. Gu, D. Bickson, and C. Guestrin. 2012. PowerGraph: Distributed graph-parallel computation on natural graphs. In Proceedings of the 10th USENIX Symposium on Operating Systems Design and Implementation.USENIX Association, 17\u201330."},{"key":"e_1_3_4_61_2","first-page":"11:1\u201311:15","volume-title":"Proceedings of the 18th Symposium on Experimental Algorithms","author":"Gottesb\u00fcren L.","year":"2020","unstructured":"L. Gottesb\u00fcren, M. Hamann, S.Schlag, and D. Wagner. 2020. Advanced flow-based multilevel hypergraph partitioning. In Proceedings of the 18th Symposium on Experimental Algorithms. Schloss Dagstuhl \u2013 Leibniz-Zentrum fuer Informatik, 11:1\u201311:15."},{"key":"e_1_3_4_62_2","first-page":"52:1\u201352:17","volume-title":"Proceedings of the 27th Annual European Symposium on Algorithms.","author":"Gottesb\u00fcren L.","year":"2019","unstructured":"L. Gottesb\u00fcren, M. Hamann, and D. Wagner. 2019. Evaluation of a flow-based hypergraph bipartitioning algorithm. In Proceedings of the 27th Annual European Symposium on Algorithms.Schloss Dagstuhl \u2013 Leibniz-Zentrum fuer Informatik, 52:1\u201352:17."},{"key":"e_1_3_4_63_2","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611976472.2"},{"key":"e_1_3_4_64_2","doi-asserted-by":"crossref","unstructured":"L. Gottesb\u00fcren T. Heuer P. Sanders and S. Schlag. 2021. Shared-memory n-level hypergraph partitioning. arXiv:2104.08107. Retrieved from https:\/\/arxiv.org\/abs\/2104.08107.","DOI":"10.1137\/1.9781611976472.2"},{"key":"e_1_3_4_65_2","unstructured":"L. Gottesb\u00fcren T. Heuer P. Sanders C. Schulz and D. Seemaier. 2021. Deep multilevel graph partitioning. arXiv:2105.02022. Retrieved from https:\/\/arxiv.org\/abs\/2105.02022."},{"key":"e_1_3_4_66_2","doi-asserted-by":"publisher","DOI":"10.22331\/q-2021-03-15-410"},{"key":"e_1_3_4_67_2","doi-asserted-by":"publisher","DOI":"10.1145\/3173045"},{"key":"e_1_3_4_68_2","doi-asserted-by":"publisher","DOI":"10.1109\/43.644609"},{"key":"e_1_3_4_69_2","doi-asserted-by":"publisher","DOI":"10.1145\/2627534.2627563"},{"key":"e_1_3_4_70_2","first-page":"12","volume-title":"Proceedings of the IEEE International Conference on Cloud Engineering","author":"Heintz B.","year":"2019","unstructured":"B. Heintz, R. Hong, S. Singh, G. Khandelwal, C. Tesdahl, and A. Chandra. 2019. MESH: A flexible distributed hypergraph processing system. In Proceedings of the IEEE International Conference on Cloud Engineering. 12\u201322."},{"key":"e_1_3_4_71_2","doi-asserted-by":"publisher","DOI":"10.1137\/S1064827596300656"},{"key":"e_1_3_4_72_2","volume-title":"Label Propagation for Hypergraph Partitioning","author":"Henne V.","year":"2015","unstructured":"V. Henne. 2015. Label Propagation for Hypergraph Partitioning. Master\u2019s thesis. Karlsruhe Institute of Technology."},{"key":"e_1_3_4_73_2","volume-title":"Engineering Initial Partitioning Algorithms for direct \\(k\\) -way Hypergraph Partitioning","author":"Heuer T.","year":"2015","unstructured":"T. Heuer. 2015. Engineering Initial Partitioning Algorithms for direct \\(k\\) -way Hypergraph Partitioning. Bachelor Thesis. Karlsruhe Institute of Technology."},{"key":"e_1_3_4_74_2","volume-title":"High Quality Hypergraph Partitioning via Max-Flow-Min-Cut Computations","author":"Heuer T.","year":"2018","unstructured":"T. Heuer. 2018. High Quality Hypergraph Partitioning via Max-Flow-Min-Cut Computations. Master\u2019s thesis. Karlsruhe Institute of Technology."},{"key":"e_1_3_4_75_2","first-page":"8:1\u20138:20","volume-title":"Proceedings of the 19th International Symposium on Experimental Algorithms.","author":"Heuer T.","year":"2021","unstructured":"T. Heuer, N. Maas, and S. Schlag. 2021. Multilevel hypergraph partitioning with vertex weights revisited. In Proceedings of the 19th International Symposium on Experimental Algorithms.8:1\u20138:20."},{"key":"e_1_3_4_76_2","first-page":"1:1\u20131:19","volume-title":"Proceedings of the 17th International Symposium on Experimental Algorithms (Leibniz International Proceedings in Informatics)","volume":"103","author":"Heuer T.","year":"2018","unstructured":"T. Heuer, P. Sanders, and S. Schlag. 2018. Network flow-based refinement for multilevel hypergraph partitioning. In Proceedings of the 17th International Symposium on Experimental Algorithms (Leibniz International Proceedings in Informatics). G. D\u2019Angelo (Ed.), Vol. 103. Schloss Dagstuhl \u2013 Leibniz-Zentrum f\u00fcr Informatik, 1:1\u20131:19."},{"issue":"1","key":"e_1_3_4_77_2","first-page":"2.3:1\u20132.3:36","article-title":"Network flow-based refinement for multilevel hypergraph partitioning","volume":"24","author":"Heuer T.","year":"2019","unstructured":"T. Heuer, P. Sanders, and S. Schlag. 2019. Network flow-based refinement for multilevel hypergraph partitioning. ACM Journal of Experimental Algorithmics 24, 1(2019), 2.3:1\u20132.3:36.","journal-title":"ACM Journal of Experimental Algorithmics"},{"key":"e_1_3_4_78_2","first-page":"21:1\u201321:19","volume-title":"Proceedings of the 16th International Symposium on Experimental Algorithms (Leibniz International Proceedings in Informatics)","author":"Heuer T.","year":"2017","unstructured":"T. Heuer and S. Schlag. 2017. Improving coarsening schemes for hypergraph partitioning by exploiting community structure. In Proceedings of the 16th International Symposium on Experimental Algorithms (Leibniz International Proceedings in Informatics). Schloss Dagstuhl \u2013 Leibniz-Zentrum f\u00fcr Informatik, 21:1\u201321:19."},{"key":"e_1_3_4_79_2","first-page":"87","volume-title":"Proceedings of the VLSI Circuit Layout: Theory and Design","author":"Hu T. C.","year":"1985","unstructured":"T. C. Hu and K. Moerder. 1985. Multiterminal flows in a hypergraph. In Proceedings of the VLSI Circuit Layout: Theory and Design. T. C. Hu and E. S. Kuh (Eds.), IEEE, Chapter 3, 87\u201393."},{"key":"e_1_3_4_80_2","unstructured":"C. Huang F. Zhang M. Newman J. Cai X. Gao Z. Tian J. Wu H. Xu H. Yu B. Yuan et\u00a0al. 2020. Classical simulation of quantum supremacy circuits. arXiv:2005.06787. Retrieved from https:\/\/arxiv.org\/abs\/2005.06787."},{"key":"e_1_3_4_81_2","first-page":"650","volume-title":"Proceedings of the 32nd International Parallel and Distributed Processing Symposium","author":"H\u00fcbschle-Schneider L.","year":"2018","unstructured":"L. H\u00fcbschle-Schneider and P. Sanders. 2018. Communication efficient checking of big data operations. In Proceedings of the 32nd International Parallel and Distributed Processing Symposium. 650\u2013659."},{"key":"e_1_3_4_82_2","first-page":"604","volume-title":"Proceedings of the 29th ACM Symposium on Theory of Computing","author":"Indyk P.","year":"1998","unstructured":"P. Indyk and R. Motwani. 1998. Approximate nearest neighbors: Towards removing the curse of dimensionality. In Proceedings of the 29th ACM Symposium on Theory of Computing. ACM, 604\u2013613."},{"key":"e_1_3_4_83_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.compchemeng.2019.03.009"},{"key":"e_1_3_4_84_2","article-title":"HyperX: A scalable hypergraph framework","author":"Jiang W.","year":"2018","unstructured":"W. Jiang, J. Qi, J. X. Yu, J. Huang, and R. Zhang. 2018. HyperX: A scalable hypergraph framework. IEEE Transactions on Knowledge and Data Engineering (2018).","journal-title":"IEEE Transactions on Knowledge and Data Engineering"},{"key":"e_1_3_4_85_2","doi-asserted-by":"publisher","DOI":"10.14778\/3137628.3137650"},{"key":"e_1_3_4_86_2","first-page":"125","volume-title":"Multilevel Hypergraph Partitioning","author":"Karypis G.","year":"2003","unstructured":"G. Karypis. 2003. Multilevel Hypergraph Partitioning. Springer, 125\u2013154."},{"key":"e_1_3_4_87_2","volume-title":"hMETIS - Hypergraph & Circuit Partitioning","author":"Karypis G.","year":"2019","unstructured":"G. Karypis. 2019. hMETIS - Hypergraph & Circuit Partitioning. Retrieved from http:\/\/glaros.dtc.umn.edu\/gkhome\/metis\/hmetis\/overview."},{"key":"e_1_3_4_88_2","doi-asserted-by":"publisher","DOI":"10.1109\/92.748202"},{"key":"e_1_3_4_89_2","doi-asserted-by":"publisher","DOI":"10.1137\/S1064827595287997"},{"key":"e_1_3_4_90_2","volume-title":"Multilevel \\(k\\) -way Hypergraph Partitioning","author":"Karypis G.","year":"1998","unstructured":"G. Karypis and V. Kumar. 1998. Multilevel \\(k\\) -way Hypergraph Partitioning. Technical Report 98-036. University of Minnesota."},{"issue":"3","key":"e_1_3_4_91_2","doi-asserted-by":"crossref","first-page":"285","DOI":"10.1155\/2000\/19436","article-title":"Multilevel k-way hypergraph partitioning","author":"Karypis G.","year":"2000","unstructured":"G. Karypis and V. Kumar. 2000. Multilevel k-way hypergraph partitioning. VLSI Design3 (2000), 285\u2013300.","journal-title":"VLSI Design"},{"key":"e_1_3_4_92_2","doi-asserted-by":"publisher","DOI":"10.1109\/TC.1984.1676460"},{"key":"e_1_3_4_93_2","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-014-0362-1"},{"key":"e_1_3_4_94_2","article-title":"Community detection algorithms: A comparative analysis","volume":"80","author":"Lancichinetti A.","year":"2009","unstructured":"A. Lancichinetti and S. Fortunato. 2009. Community detection algorithms: A comparative analysis. Physical Review 80, 5(2009).","journal-title":"Physical Review"},{"key":"e_1_3_4_95_2","doi-asserted-by":"publisher","DOI":"10.1002\/net.3230030306"},{"key":"e_1_3_4_96_2","doi-asserted-by":"publisher","DOI":"10.5555\/92429"},{"key":"e_1_3_4_97_2","first-page":"68","volume-title":"Finding Similar Items (2 ed.)","author":"Leskovec J.","year":"2014","unstructured":"J. Leskovec, A. Rajaraman, and J. D. Ullman. 2014. Finding Similar Items (2 ed.). Cambridge University Press, 68\u2013122."},{"issue":"1","key":"e_1_3_4_98_2","first-page":"14:1\u201314:21","article-title":"A simple yet effective balanced edge partition model for parallel computing","volume":"1","author":"Li L.","year":"2017","unstructured":"L. Li, R. Geda, A. B. Hayes, Y. Chen, P. Chaudhari, E. Z. Zhang, and M. Szegedy. 2017. A simple yet effective balanced edge partition model for parallel computing. Proceedings of the ACM on Measurement and Analysis of Computing Systems 1, 1 (2017), 14:1\u201314:21.","journal-title":"Proceedings of the ACM on Measurement and Analysis of Computing Systems"},{"key":"e_1_3_4_99_2","doi-asserted-by":"publisher","DOI":"10.1145\/1772690.1772759"},{"issue":"1","key":"e_1_3_4_100_2","doi-asserted-by":"crossref","first-page":"50","DOI":"10.1109\/43.673632","article-title":"Network-flow-based multiway partitioning with area and pin constraints","volume":"17","author":"Liu H.","year":"1998","unstructured":"H. Liu and M. D. F. Wong. 1998. Network-flow-based multiway partitioning with area and pin constraints. IEEE Transactions on Computer-Aided Design of Integrated Circuits & Systems 17, 1(1998), 50\u201359.","journal-title":"IEEE Transactions on Computer-Aided Design of Integrated Circuits & Systems"},{"key":"e_1_3_4_101_2","first-page":"41","volume-title":"Proceedings of the 5th Pragmatics of SAT Workshop","author":"Mann Z. \u00c1.","year":"2014","unstructured":"Z. \u00c1. Mann and P. A. Papp. 2014. Formula partitioning revisited. In Proceedings of the 5th Pragmatics of SAT Workshop. 41\u201356."},{"key":"e_1_3_4_102_2","volume-title":"HYPE","author":"Mayer R.","year":"2019","unstructured":"R. Mayer and L. Epple. 2019. HYPE. Retrieved from https:\/\/github.com\/mayerrn\/HYPE."},{"issue":"2","key":"e_1_3_4_103_2","doi-asserted-by":"crossref","first-page":"25:1\u201325:39","DOI":"10.1145\/2818185","article-title":"Thinking like a vertex: A survey of vertex-centric frameworks for large-scale distributed graph processing","volume":"48","author":"McCune R. R.","year":"2015","unstructured":"R. R. McCune, T. Weninger, and G. Madey. 2015. Thinking like a vertex: A survey of vertex-centric frameworks for large-scale distributed graph processing. ACM Computing Surveys 48, 2(2015), 25:1\u201325:39.","journal-title":"ACM Computing Surveys"},{"key":"e_1_3_4_104_2","first-page":"351","volume-title":"Proceedings of the 13th International Symposium on Experimental Algorithms.","author":"Meyerhenke H.","year":"2014","unstructured":"H. Meyerhenke, P. Sanders, and C. Schulz. 2014. Partitioning complex networks via size-constrained clustering. In Proceedings of the 13th International Symposium on Experimental Algorithms.351\u2013363."},{"key":"e_1_3_4_105_2","doi-asserted-by":"publisher","DOI":"10.1007\/s10732-016-9315-8"},{"key":"e_1_3_4_106_2","first-page":"1","volume-title":"Proceedings of the International Conference on Computer-Aided Design","author":"Neto W. L.","year":"2019","unstructured":"W. L. Neto, M. Austin, S. Temple, L. G. Amar\u00f9, X. Tang, and P. Gaillardon. 2019. LSOracle: A logic synthesis framework driven by artificial intelligence: Invited paper. In Proceedings of the International Conference on Computer-Aided Design. 1\u20136."},{"key":"e_1_3_4_107_2","article-title":"Analysis of weighted networks","volume":"70","author":"Newman M. E. J.","year":"2004","unstructured":"M. E. J. Newman. 2004. Analysis of weighted networks. Physical Review 70, 5(2004).","journal-title":"Physical Review"},{"key":"e_1_3_4_108_2","article-title":"Finding and evaluating community structure in networks","volume":"69","author":"Newman M. E. J.","year":"2004","unstructured":"M. E. J. Newman and M. Girvan. 2004. Finding and evaluating community structure in networks. Physical Review 69, 2(2004).","journal-title":"Physical Review"},{"key":"e_1_3_4_109_2","first-page":"278","volume-title":"Proceedings of the 18th European Symposium on Algorithms","author":"Osipov V.","year":"2010","unstructured":"V. Osipov and P. Sanders. 2010. n-level graph partitioning. In Proceedings of the 18th European Symposium on Algorithms. 278\u2013289."},{"key":"e_1_3_4_110_2","unstructured":"D. A. Papa and I. L. Markov. 2006. Illustration of Partitioning Formats and Partitioner Performance Comparison. Retrieved from http:\/\/vlsicad.eecs.umich.edu\/BK\/PART\/illustrations\/."},{"key":"e_1_3_4_111_2","volume-title":"Proceedings of the Handbook of Approximation Algorithms and Metaheuristics","author":"Papa D. A.","year":"2007","unstructured":"D. A. Papa and I. L. Markov. 2007. Hypergraph partitioning and clustering. In Proceedings of the Handbook of Approximation Algorithms and Metaheuristics."},{"key":"e_1_3_4_112_2","volume-title":"Experiments on Sparse Matrix Partitioning","author":"Riyavong S.","year":"2003","unstructured":"S. Riyavong. 2003. Experiments on Sparse Matrix Partitioning. Technical Report CERFACS Working Note WN\/PA\/03\/32. CERFACS."},{"key":"e_1_3_4_113_2","doi-asserted-by":"publisher","DOI":"10.1109\/12.8730"},{"key":"e_1_3_4_114_2","doi-asserted-by":"publisher","DOI":"10.1109\/12.260640"},{"key":"e_1_3_4_115_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-23719-5_40"},{"key":"e_1_3_4_116_2","first-page":"16","volume-title":"Proceedings of the 12th Workshop on Algorithm Engineering and Experimentation","author":"Sanders P.","year":"2012","unstructured":"P. Sanders and C. Schulz. 2012. Distributed evolutionary graph partitioning. In Proceedings of the 12th Workshop on Algorithm Engineering and Experimentation. 16\u201329."},{"key":"e_1_3_4_117_2","first-page":"164","volume-title":"Proceedings of the 12th International Symposium on Experimental Algorithms.","author":"Sanders P.","year":"2013","unstructured":"P. Sanders and C. Schulz. 2013. Think locally, act globally: Highly balanced graph partitioning. In Proceedings of the 12th International Symposium on Experimental Algorithms.Springer, 164\u2013175."},{"key":"e_1_3_4_118_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.cosrev.2007.05.001"},{"key":"e_1_3_4_119_2","doi-asserted-by":"publisher","DOI":"10.5445\/IR\/1000098881"},{"key":"e_1_3_4_120_2","doi-asserted-by":"publisher","DOI":"10.5445\/IR\/1000105953"},{"key":"e_1_3_4_121_2","first-page":"53","volume-title":"Proceedings of the 18th Workshop on Algorithm Engineering and Experiments","author":"Schlag S.","year":"2016","unstructured":"S. Schlag, V. Henne, T. Heuer, H. Meyerhenke, P. Sanders, and C. Schulz. 2016. \\(k\\) -way hypergraph partitioning via \\(n\\) -level recursive bisection. In Proceedings of the 18th Workshop on Algorithm Engineering and Experiments. SIAM, 53\u201367."},{"key":"e_1_3_4_122_2","first-page":"211","volume-title":"Proceedings of the 21st Workshop on Algorithm Engineering & Experiments.","author":"Schlag S.","year":"2019","unstructured":"S. Schlag, C. Schulz, D. Seemaier, and D. Strash. 2019. Scalable edge partitioning. In Proceedings of the 21st Workshop on Algorithm Engineering & Experiments.SIAM, 211\u2013225."},{"key":"e_1_3_4_123_2","volume-title":"High Quality Graph Partitioning","author":"Schulz C.","year":"2013","unstructured":"C. Schulz. 2013. High Quality Graph Partitioning. Ph.D. Dissertation. Karlsruhe Institute of Technology. Retrieved from http:\/\/digbib.ubka.uni-karlsruhe.de\/volltexte\/1000035713."},{"key":"e_1_3_4_124_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-63962-8_312-2"},{"key":"e_1_3_4_125_2","first-page":"57","volume-title":"Proceedings of the 9th Conference on Design Automation.","author":"Schweikert D. G.","year":"1972","unstructured":"D. G. Schweikert and B. W. Kernighan. 1972. A proper model for the partitioning of electrical circuits. In Proceedings of the 9th Conference on Design Automation.57\u201362."},{"key":"e_1_3_4_126_2","volume-title":"Aggregative Coarsening for Multilevel Hypergraph Partitioning","author":"Shaydulin R.","year":"2019","unstructured":"R. Shaydulin. 2019. Aggregative Coarsening for Multilevel Hypergraph Partitioning. Retrieved from https:\/\/github.com\/rsln-s\/aggregative-coarsening-for-multilevel-hypergraph-partitioning."},{"key":"e_1_3_4_127_2","first-page":"2:1\u20132:15","volume-title":"Proceedings of the 17th International Symposium on Experimental Algorithms.","author":"Shaydulin R.","year":"2018","unstructured":"R. Shaydulin and I. Safro. 2018. Aggregative coarsening for multilevel hypergraph partitioning. In Proceedings of the 17th International Symposium on Experimental Algorithms.2:1\u20132:15."},{"key":"e_1_3_4_128_2","unstructured":"R. Shaydulin and I. Safro. 2018. Aggregative coarsening for multilevel hypergraph partitioning. arXiv:1802.09610. Retrieved from https:\/\/arxiv.org\/abs\/1802.09610."},{"key":"e_1_3_4_129_2","doi-asserted-by":"publisher","DOI":"10.1137\/17M1152735"},{"key":"e_1_3_4_130_2","doi-asserted-by":"publisher","DOI":"10.1023\/B:JOGO.0000042115.44455.f3"},{"key":"e_1_3_4_131_2","first-page":"114","volume-title":"Proceedings of the 3rd International Symposium on Parallel and Distributed Computing.","author":"Trifunovi\u0107 A.","year":"2004","unstructured":"A. Trifunovi\u0107 and W. J. Knottenbelt. 2004. A parallel algorithm for multilevel k-way hypergraph partitioning. In Proceedings of the 3rd International Symposium on Parallel and Distributed Computing.114\u2013121."},{"key":"e_1_3_4_132_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.jpdc.2007.11.002"},{"key":"e_1_3_4_133_2","doi-asserted-by":"publisher","DOI":"10.1137\/S1064827502410463"},{"key":"e_1_3_4_134_2","doi-asserted-by":"publisher","DOI":"10.1137\/S0036144502409019"},{"key":"e_1_3_4_135_2","doi-asserted-by":"publisher","DOI":"10.1145\/2228360.2228500"},{"key":"e_1_3_4_136_2","doi-asserted-by":"publisher","DOI":"10.1023\/B:ANOR.0000039525.80601.15"},{"key":"e_1_3_4_137_2","first-page":"505","volume-title":"Proceedings of the International Conference on Computer-Aided Design","author":"Wichlund S.","year":"1998","unstructured":"S. Wichlund and E. Aas. 1998. On multilevel circuit partitioning. In Proceedings of the International Conference on Computer-Aided Design. 505\u2013511."},{"key":"e_1_3_4_138_2","doi-asserted-by":"publisher","DOI":"10.2307\/3001968"},{"key":"e_1_3_4_139_2","doi-asserted-by":"publisher","DOI":"10.1109\/43.552086"}],"container-title":["ACM Journal of Experimental Algorithmics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3529090","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,2,10]],"date-time":"2023-02-10T14:04:26Z","timestamp":1676037866000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3529090"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,12,31]]},"references-count":138,"alternative-id":["10.1145\/3529090"],"URL":"http:\/\/dx.doi.org\/10.1145\/3529090","relation":{},"ISSN":["1084-6654","1084-6654"],"issn-type":[{"value":"1084-6654","type":"print"},{"value":"1084-6654","type":"electronic"}],"subject":[],"published":{"date-parts":[[2022,12,31]]}}}