{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T04:17:21Z","timestamp":1750306641788,"version":"3.41.0"},"reference-count":25,"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"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["ACM J. Exp. Algorithmics"],"published-print":{"date-parts":[[2015,2,3]]},"abstract":"<jats:p>To improve the quality and efficiency of hypergraph-based matrix partitioners, we investigate high-quality matchings in column intersection graphs of large sparse binary matrices. We show that such algorithms have a natural decomposition in an integer-weighted graph-matching function and a neighbor-finding function and study the performance of 16 combinations of these functions. We improve upon the original matching algorithm of the Mondriaan matrix partitioner: by using PGA\u2019, we improve the average matching quality from 95.3% to 97.4% of the optimum value; by using our new neighbor-finding heuristic, we obtain comparable quality and speedups of up to a factor of 19.6.<\/jats:p>","DOI":"10.1145\/2616587","type":"journal-article","created":{"date-parts":[[2014,6,20]],"date-time":"2014-06-20T13:05:51Z","timestamp":1403269551000},"source":"Crossref","is-referenced-by-count":0,"title":["Efficient Matching for Column Intersection Graphs"],"prefix":"10.1145","volume":"19","author":[{"given":"B. O. Fagginger","family":"Auer","sequence":"first","affiliation":[{"name":"Utrecht University, the Netherlands"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"R. H.","family":"Bisseling","sequence":"additional","affiliation":[{"name":"Utrecht University, the Netherlands"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2015,1,7]]},"reference":[{"volume-title":"Parallel Scientific Computation: A Structured Approach Using BSP and MPI","author":"Bisseling R. H.","key":"e_1_2_1_1_1"},{"volume-title":"Two-dimensional approaches to sparse matrix partitioning","author":"Bisseling R. H.","key":"e_1_2_1_2_1","doi-asserted-by":"crossref","DOI":"10.1201\/b11644-13"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1109\/71.780863"},{"key":"e_1_2_1_4_1","unstructured":"\u00dc. V. \u00c7ataly\u00fcrek and C. Aykanat. 1999. PaToH: A Multilevel Hypergraph Partitioning Tool version 3.0. Bilkent University Department of Computer Engineering Ankara Turkey. Available at http:\/\/bmi.osu.edu\/&sim;umit\/software.htm.  \u00dc. V. \u00c7ataly\u00fcrek and C. Aykanat. 1999. PaToH: A Multilevel Hypergraph Partitioning Tool version 3.0. Bilkent University Department of Computer Engineering Ankara Turkey. Available at http:\/\/bmi.osu.edu\/&sim;umit\/software.htm."},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1109\/IPDPS.2012.81"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/2049662.2049663"},{"volume-title":"Proc. IPDPS 2006","year":"2006","author":"Devine K. D.","key":"e_1_2_1_7_1"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.entcs.2011.06.003"},{"volume":"2764","volume-title":"Proc. Approx\/Random. LNCS","author":"Drake D. E.","key":"e_1_2_1_9_1"},{"key":"e_1_2_1_10_1","volume-title":"Proc. Workshop Exp. Alg.","volume":"2647","author":"Drake D. E.","year":"2003"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0020-0190(02)00393-9"},{"volume-title":"Scaling algorithms for approximate and exact maximum weight matching. CoRR abs\/1112.0790","year":"2011","author":"Duan R.","key":"e_1_2_1_12_1"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/229473.229480"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.6028\/jres.069B.013"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.4153\/CJM-1965-045-4"},{"volume-title":"Proc. 19th IEEE DAC. IEEE","year":"1982","author":"Fiduccia C. M.","key":"e_1_2_1_16_1"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/115234.115366"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0036144504444711"},{"volume-title":"Proc. IPDPS 2010","year":"2010","author":"Holtgrewe M.","key":"e_1_2_1_19_1"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1002\/j.1538-7305.1970.tb01770.x"},{"key":"e_1_2_1_21_1","volume-title":"Proc. Workshop Exp. Alg.","volume":"4525","author":"Maue J.","year":"2007"},{"volume-title":"Proc. IPDPS 2014","year":"2014","author":"Pelt D. M.","key":"e_1_2_1_22_1"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ipl.2004.05.007"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.5555\/1764891.1764924"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0036144502409019"}],"container-title":["ACM Journal of Experimental Algorithmics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2616587","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2616587","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T06:56:00Z","timestamp":1750229760000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2616587"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015,1,7]]},"references-count":25,"alternative-id":["10.1145\/2616587"],"URL":"https:\/\/doi.org\/10.1145\/2616587","relation":{},"ISSN":["1084-6654","1084-6654"],"issn-type":[{"type":"print","value":"1084-6654"},{"type":"electronic","value":"1084-6654"}],"subject":[],"published":{"date-parts":[[2015,1,7]]}}}