{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T17:28:24Z","timestamp":1787333304427,"version":"build-2736575974"},"reference-count":54,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"2","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Sci. Comput."],"published-print":{"date-parts":[[2012,1]]},"abstract":"<jats:p>The modeling flexibility provided by hypergraphs has drawn a lot of interest from the combinatorial scientific community, leading to novel models and algorithms, their applications, and development of associated tools. Hypergraphs are now a standard tool in combinatorial scientific computing. The modeling flexibility of hypergraphs, however, comes at a cost: algorithms on hypergraphs are inherently more complicated than those on graphs, which sometimes translates to nontrivial increases in processing times. Neither the modeling flexibility of hypergraphs nor the runtime efficiency of graph algorithms can be overlooked. Therefore, the new research thrust should be how to cleverly trade off between the two. This work addresses one method for this trade-off by solving the hypergraph partitioning problem by finding vertex separators on graphs. Specifically, we investigate how to solve the hypergraph partitioning problem by seeking a vertex separator on its net intersection graph (NIG), where each net of the hypergraph is represented by a vertex, and two vertices share an edge if their nets have a common vertex. We propose a vertex-weighting scheme to attain good node-balanced hypergraphs, since the NIG model cannot preserve node-balancing information. Vertex-removal and vertex-splitting techniques are described to optimize cut-net and connectivity metrics, respectively, under the recursive bipartitioning paradigm. We also developed implementations of our proposed hypergraph partitioning formulations by adopting and modifying a state-of-the-art graph partitioning by vertex separator tool onmetis. Experiments conducted on a large collection of sparse matrices demonstrate the effectiveness of our proposed techniques.<\/jats:p>","DOI":"10.1137\/100810022","type":"journal-article","created":{"date-parts":[[2012,3,29]],"date-time":"2012-03-29T18:55:17Z","timestamp":1333047317000},"page":"A970-A992","source":"Crossref","is-referenced-by-count":15,"title":["Partitioning Hypergraphs in Scientific Computing Applications through Vertex Separators on Graphs"],"prefix":"10.1137","volume":"34","author":[{"given":"Enver","family":"Kayaaslan","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Ali","family":"Pinar","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"\u00dcmit","family":"\u00c7ataly\u00fcrek","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Cevdet","family":"Aykanat","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2012,3,29]]},"reference":[{"key":"R1","unstructured":"K. Akbudak, E. Kayaaslan, and C. Aykanat,\n                      Hypergraph-Partitioning-Based Models and Methods for Exploiting Cache Locality in Sparse Matrix-Vector Multiplication\n                      , Technical report BU-CE-1201, Computer Engineering Department, Bilkent University, Ankara, Turkey, 2012."},{"key":"R2","doi-asserted-by":"publisher","DOI":"10.1016\/0167-9260(95)00008-4"},{"key":"R3","doi-asserted-by":"publisher","DOI":"10.1137\/S1064827502401953"},{"key":"R4","doi-asserted-by":"publisher","DOI":"10.1016\/j.parco.2006.08.005"},{"key":"R5","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(92)90140-Q"},{"key":"R6","doi-asserted-by":"publisher","DOI":"10.1109\/TPDS.2007.253277"},{"key":"R7","doi-asserted-by":"crossref","unstructured":"\u00dc. V. \u00c7ataly\u00fcrek and C. Aykanat,\n                      Decomposing irregularly sparse matrices for parallel matrix-vector multiplications\n                      , in Proceedings of the 3rd International Symposium on Solving Irregularly Structured Problems in Parallel (Irregular'96), Lecture Notes in Comput. Sci. 1117, Springer-Verlag, New York, 1996, pp. 75\u201386.","DOI":"10.1007\/BFb0030098"},{"key":"R8","doi-asserted-by":"publisher","DOI":"10.1109\/71.780863"},{"key":"R9","unstructured":"\u00dc. V. \u00c7ataly\u00fcrek and C. Aykanat,\n                      PaToH: A Multilevel Hypergraph Partitioning Tool, Version\n                      3.0, Department of Computer Engineering, Bilkent University, Ankara, 06533 Turkey; also available from http:\/\/bmi.osu.edu\/~umit\/software.htm, 1999."},{"key":"R10","unstructured":"\u00dc. V. \u00c7ataly\u00fcrek and C. Aykanat,\n                      A fine-grain hypergraph model for 2D decomposition of sparse matrices\n                      , in Proceedings of the 15th International Parallel and Distributed Processing Symposium (IPDPS), San Francisco, CA, 2001."},{"key":"R11","doi-asserted-by":"crossref","unstructured":"\u00dc. V. \u00c7ataly\u00fcrek and C. Aykanat,\n                      A hypergraph-partitioning approach for coarse-grain decomposition\n                      , in ACM\/IEEE SC2001, Denver, CO, 2001.","DOI":"10.1145\/582034.582062"},{"key":"R12","doi-asserted-by":"publisher","DOI":"10.1137\/080737770"},{"key":"R13","doi-asserted-by":"crossref","unstructured":"P. K. Chan, D. F. Schlag, and J. Y. Zien,\n                      Spectral K-way ratio-cut partitioning and clustering\n                      , in Proceedings of the 30th Design Automation Conference, ACM\/IEEE, 1993, pp. 749\u2013754.","DOI":"10.1145\/157485.165117"},{"key":"R14","unstructured":"C. Chang, T. Kurc, A. Sussman, \u00dc. V. \u00c7ataly\u00fcrek, and J. Saltz,\n                      A hypergraph-based workload partitioning strategy for parallel data aggregation\n                      , in Proceedings of the Eleventh SIAM Conference on Parallel Processing for Scientific Computing, SIAM, Philadelphia, 2001."},{"key":"R15","doi-asserted-by":"crossref","unstructured":"J. Cong, L. Hagen, and A. B. Kahng,\n                      Net partitions yield better module partitions\n                      , in Proceedings of the 29th ACM\/IEEE Design Automation Conference, ACM, New York IEEE, Washington, DC, 1992, pp. 47\u201352.","DOI":"10.1109\/DAC.1992.227863"},{"key":"R16","doi-asserted-by":"crossref","unstructured":"J. Cong, W. Labio, and N. Shivakumar,\n                      Multi-way VLSI circuit partitioning based on dual net representation\n                      , in Proceedings of the IEEE International Conference on Computer-Aided Design, IEEE, Washington, DC, 1994, pp. 56\u201362.","DOI":"10.1109\/ICCAD.1994.629744"},{"key":"R17","doi-asserted-by":"crossref","unstructured":"T. Davis,\n                      The University of Florida Sparse Matrix Collection\n                      , ACM Trans. Math. Software, 38 (2011).","DOI":"10.1145\/2049662.2049663"},{"key":"R18","doi-asserted-by":"crossref","unstructured":"K. Devine, E. Boman, R. Heaphy, R. Bisseling, and U. Catalyurek,\n                      Parallel hypergraph partitioning for scientific computing\n                      , in Proceedings of the 20th International Parallel and Distributed Processing Symposium (IPDPS), IEEE, Washington, DC, 2006.","DOI":"10.1109\/IPDPS.2006.1639359"},{"key":"R19","doi-asserted-by":"publisher","DOI":"10.1016\/j.jpdc.2004.03.017"},{"key":"R20","doi-asserted-by":"crossref","unstructured":"C. M. Fiduccia and R. M. Mattheyses,\n                      A linear-time heuristic for improving network partitions\n                      , in Proceedings of the 19th ACM\/IEEE Design Automation Conference, ACM, New York, IEEE, Washington, DC, 1982, pp. 175\u2013181.","DOI":"10.1109\/DAC.1982.1585498"},{"key":"R21","unstructured":"A. George and J. W. H. Liu,\n                      Computer Solution of Large Sparse Positive Definite Systems\n                      , Prentice-Hall, Englewood Cliffs, NJ, 1981."},{"key":"R22","doi-asserted-by":"publisher","DOI":"10.1137\/0710032"},{"key":"R23","doi-asserted-by":"publisher","DOI":"10.1109\/TCAD.1982.1269996"},{"key":"R24","doi-asserted-by":"publisher","DOI":"10.1109\/43.144852"},{"key":"R25","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(93)90115-P"},{"key":"R26","doi-asserted-by":"crossref","unstructured":"A. B. Kahng,\n                      Fast hypergraph partition\n                      , in Proceedings of the 26th ACM\/IEEE Design Automation Conference, ACM, New York, IEEE, Washington, DC, 1989, pp. 762\u2013766.","DOI":"10.1145\/74382.74524"},{"key":"R27","unstructured":"G. Karypis and V. Kumar,\n                      MeTiS: A Software Package for Partitioning Unstructured Graphs, Partitioning Meshes, and Computing Fill-Reducing Orderings of Sparse Matrices, Version\n                      4.0, Department of Computer Science and Engineering, Army HPC Research Center, University of Minnesota, MN, 1998."},{"key":"R28","unstructured":"G. Karypis, V. Kumar, R. Aggarwal, and S. Shekhar,\n                      hMeTiS: A Hypergraph Partitioning Package, Version\n                      1.0.1, Department of Computer Science and Engineering, Army HPC Research Center, University of Minnesota, MN, 1998."},{"key":"R29","doi-asserted-by":"publisher","DOI":"10.1109\/TPDS.2006.105"},{"key":"R30","doi-asserted-by":"publisher","DOI":"10.1016\/j.jpdc.2006.11.004"},{"key":"R31","unstructured":"E. Kayaaslan, A. Pinar, \u00dc. V. \u00c7ataly\u00fcrek, and C. Aykanat,\n                      Hypergraph Partitioning Through Vertex Separators on Graphs\n                      , Technical report BU-CE-1017, Computer Engineering Department, Bilkent University, Ankara, Turkey, 2010; also available from http:\/\/bmi.osu.edu\/hpc\/publications.html."},{"key":"R32","doi-asserted-by":"publisher","DOI":"10.1002\/j.1538-7305.1970.tb01770.x"},{"key":"R33","unstructured":"G. Khanna, N. Vydyanathan, T. Kurc, \u00dc. \u00c7ataly\u00fcrek, P. Wyckoff, J. Saltz, and P. Sadayappan,\n                      A hypergraph partitioning based approach for scheduling of tasks with batch-shared I\/O\n                      , in Proceedings of the 5th IEEE\/ACM International Symposium on Cluster Computing and the Grid (CCGrid 2005), IEEE, Washington, DC, ACM, New York, 2005."},{"key":"R34","unstructured":"E. Lawler,\n                      Combinatorial Optimization: Networks and Matroids\n                      , Holt, Rinehart, and Winston, New York, 1976."},{"key":"R35","unstructured":"C. E. Leiserson and J. G. Lewis,\n                      Orderings for parallel sparse symmetric matrix factorization\n                      , in Proceedings of the 3rd SIAM Conference on Parallel Processing for Scientific Computing, SIAM, Philadelphia, 1987, pp. 27\u201331."},{"key":"R36","doi-asserted-by":"crossref","unstructured":"T. Lengauer,\n                      Combinatorial Algorithms for Integrated Circuit Layout\n                      , Wiley\u2013Teubner, Chichester, UK, 1990.","DOI":"10.1007\/978-3-322-92106-2"},{"key":"R37","doi-asserted-by":"crossref","unstructured":"A. P\u0131nar and C. Aykanat,\n                      An effective model to decompose linear programs for parallel solution\n                      , in Proceedings of the 3rd International Workshop on Applied Parallel Computing, PARA'96, Lecture Notes in Comput. Science 1184, Springer-Verlag, New York, 1997, pp. 592\u2013601.","DOI":"10.1007\/3-540-62095-8_64"},{"key":"R38","doi-asserted-by":"crossref","unstructured":"A. P\u0131nar, \u00dc. V. \u00c7ataly\u00fcrek, C. Aykanat, and M. P\u0131nar,\n                      Decomposing linear programs for parallel solution\n                      , in Proceedings of PARA 1995, Lecture Notes in Comput. Sci. 1041, Springer, New York, 1996, pp. 473\u2013482.","DOI":"10.1007\/3-540-60902-4_50"},{"key":"R39","first-page":"122","volume":"22","author":"Pinar A.","year":"2006","journal-title":"Electron. Trans. Numer. Anal.","ISSN":"https:\/\/id.crossref.org\/issn\/1097-4067","issn-type":"print"},{"key":"R40","doi-asserted-by":"crossref","unstructured":"A. Pinar and B. Hendrickson,\n                      Partitioning for complex objectives\n                      , in Proceedings of the 15th International Parallel and Distributed Processing Symposium, 2001, pp. 1232 \u20131237.","DOI":"10.1109\/IPDPS.2001.925098"},{"key":"R41","doi-asserted-by":"publisher","DOI":"10.1145\/98267.98287"},{"key":"R42","doi-asserted-by":"publisher","DOI":"10.1137\/0611030"},{"key":"R43","doi-asserted-by":"publisher","DOI":"10.1287\/opre.25.6.920"},{"key":"R44","doi-asserted-by":"crossref","unstructured":"M. M. Strout and P. D. Hovland,\n                      Metrics and models for reordering transformations\n                      , in Proceedings of the 2nd ACM SIGPLAN Workshop on Memory System Performance (MSP04) (Washington, DC), ACM, New York, 2004, pp. 23\u201334.","DOI":"10.1145\/1065895.1065899"},{"key":"R45","doi-asserted-by":"publisher","DOI":"10.1007\/s10910-009-9525-5"},{"key":"R46","doi-asserted-by":"crossref","unstructured":"A. Trifunovic and W. J. Knottenbelt,\n                      Parkway\n                      2.0:\n                      A parallel multilevel hypergraph partitioning tool\n                      , in Proceedings of the 19th International Symposium on Computer and Information Sciences (ISCIS 2004), Lecture Notes in Comput. Sci. 3280, Springer, New York, 2004, pp. 789\u2013800.","DOI":"10.1007\/978-3-540-30182-0_79"},{"key":"R47","doi-asserted-by":"crossref","unstructured":"A. Trifunovic and W. J. Knottenbelt,\n                      A general graph model for representing exact communication volume in parallel sparse matrix-vector multiplication\n                      , in Proceedings of the 21st International Symposium on Computer and Information Sciences (ISCIS 2006), 2006, pp. 813\u2013824.","DOI":"10.1007\/11902140_85"},{"key":"R48","doi-asserted-by":"publisher","DOI":"10.1137\/S1064827502410463"},{"key":"R49","doi-asserted-by":"publisher","DOI":"10.1137\/040617431"},{"key":"R50","doi-asserted-by":"publisher","DOI":"10.1137\/060662459"},{"key":"R51","doi-asserted-by":"publisher","DOI":"10.1016\/j.jpdc.2006.10.001"},{"key":"R52","doi-asserted-by":"publisher","DOI":"10.1137\/S0036144502409019"},{"key":"R53","doi-asserted-by":"crossref","unstructured":"V. Vrba, H. Espeland, P. Halvorsen, and C. Griwodz,\n                      Limits of work-stealing scheduling\n                      , in Proceedings of the 14th International Workshop on Job Scheduling Strategies for Parallel Processing (JSSPP 2009), Rome, Italy, 2009, pp. 280\u2013299.","DOI":"10.1007\/978-3-642-04633-9_15"},{"key":"R54","doi-asserted-by":"publisher","DOI":"10.1137\/080733243"}],"container-title":["SIAM Journal on Scientific Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/100810022","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T16:49:33Z","timestamp":1787330973000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/100810022"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2012,1]]},"references-count":54,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2012,1]]}},"alternative-id":["10.1137\/100810022"],"URL":"https:\/\/doi.org\/10.1137\/100810022","relation":{},"ISSN":["1064-8275","1095-7197"],"issn-type":[{"value":"1064-8275","type":"print"},{"value":"1095-7197","type":"electronic"}],"subject":[],"published":{"date-parts":[[2012,1]]}}}