{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,8,24]],"date-time":"2025-08-24T01:21:21Z","timestamp":1755998481710,"version":"3.41.0"},"reference-count":38,"publisher":"Association for Computing Machinery (ACM)","license":[{"start":{"date-parts":[[2021,4,23]],"date-time":"2021-04-23T00:00:00Z","timestamp":1619136000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/501100001659","name":"Deutsche Forschungsgemeinschaft","doi-asserted-by":"publisher","award":["NI 369\/16"],"award-info":[{"award-number":["NI 369\/16"]}],"id":[{"id":"10.13039\/501100001659","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["ACM J. Exp. Algorithmics"],"published-print":{"date-parts":[[2021,12,31]]},"abstract":"<jats:p>\n            Finding a maximum-cardinality or maximum-weight matching in (edge-weighted) undirected graphs is among the most prominent problems of algorithmic graph theory. For\n            <jats:italic>n<\/jats:italic>\n            -vertex and\n            <jats:italic>m<\/jats:italic>\n            -edge graphs, the best-known algorithms run in \u00d5(\n            <jats:italic>m<\/jats:italic>\n            \u221a\n            <jats:italic>n<\/jats:italic>\n            ) time. We build on recent theoretical work focusing on linear-time data reduction rules for finding maximum-cardinality matchings and complement the theoretical results by presenting and analyzing (thereby employing the kernelization methodology of parameterized complexity analysis) new (near-)linear-time data reduction rules for both the unweighted and the positive-integer-weighted case. Moreover, we experimentally demonstrate that these data reduction rules provide significant speedups of the state-of-the art implementations for computing matchings in real-world graphs: the average speedup factor is 4.7 in the unweighted case and 12.72 in the weighted case.\n          <\/jats:p>","DOI":"10.1145\/3439801","type":"journal-article","created":{"date-parts":[[2021,4,23]],"date-time":"2021-04-23T10:06:43Z","timestamp":1619172403000},"page":"1-30","source":"Crossref","is-referenced-by-count":8,"title":["Data Reduction for Maximum Matching on Real-World Graphs"],"prefix":"10.1145","volume":"26","author":[{"given":"Tomohiro","family":"Koana","sequence":"first","affiliation":[{"name":"TU Berlin, Germany"}]},{"given":"Viatcheslav","family":"Korenwein","sequence":"additional","affiliation":[{"name":"TU Berlin, Germany"}]},{"given":"Andr\u00e9","family":"Nichterlein","sequence":"additional","affiliation":[{"name":"TU Berlin, Germany"}]},{"given":"Rolf","family":"Niedermeier","sequence":"additional","affiliation":[{"name":"TU Berlin, Germany"}]},{"given":"Philipp","family":"Zschoche","sequence":"additional","affiliation":[{"name":"TU Berlin, Germany"}]}],"member":"320","published-online":{"date-parts":[[2021,4,23]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00224-007-1328-0"},{"key":"e_1_2_1_2_1","volume-title":"Ullman","author":"Aho Alfred V.","year":"1983","unstructured":"Alfred V. Aho , John E. Hopcroft , and Jeffrey D . Ullman . 1983 . Data Structures and Algorithms. Addison-Wesley . Alfred V. Aho, John E. Hopcroft, and Jeffrey D. Ullman. 1983. Data Structures and Algorithms. Addison-Wesley."},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2015.09.023"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1109\/SYNASC.2009.48"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10878-019-00466-2"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.7155\/jgaa.00543"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.dam.2007.03.026"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/3310228"},{"volume-title":"Parameterized Algorithms","author":"Cygan Marek","key":"e_1_2_1_9_1","unstructured":"Marek Cygan , Fedor V. Fomin , Lukasz Kowalik , Daniel Lokshtanov , D\u00e1niel Marx , Marcin Pilipczuk , Michal Pilipczuk , and Saket Saurabh . 2015. Parameterized Algorithms . Springer . Marek Cygan, Fedor V. Fomin, Lukasz Kowalik, Daniel Lokshtanov, D\u00e1niel Marx, Marcin Pilipczuk, Michal Pilipczuk, and Saket Saurabh. 2015. Parameterized Algorithms. Springer."},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/2629620"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/2529989"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/3155301"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.6028\/jres.069B.013"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.4153\/CJM-1965-045-4"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/3186898"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2017.05.017"},{"key":"e_1_2_1_17_1","volume-title":"Proceedings of the 46th International Colloquium on Automata, Languages, and Programming (ICALP\u201919)","volume":"132","author":"Hegerfeld Falko","year":"2019","unstructured":"Falko Hegerfeld and Stefan Kratsch . 2019 . On adaptive algorithms for maximum matching . In Proceedings of the 46th International Colloquium on Automata, Languages, and Programming (ICALP\u201919) (LIPIcs), Vol. 132 . Schloss Dagstuhl\u2013Leibniz-Zentrum fuer Informatik, 71:1\u201371:16. Falko Hegerfeld and Stefan Kratsch. 2019. On adaptive algorithms for maximum matching. In Proceedings of the 46th International Colloquium on Automata, Languages, and Programming (ICALP\u201919) (LIPIcs), Vol. 132. Schloss Dagstuhl\u2013Leibniz-Zentrum fuer Informatik, 71:1\u201371:16."},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611976229.1"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0377-2217(02)00071-1"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1137\/0202019"},{"key":"e_1_2_1_21_1","volume-title":"Proceedings of the 16th International Symposium on Experimental Algorithms (SEA\u201917)","volume":"75","author":"Huang Michael","year":"2017","unstructured":"Michael Huang and Clifford Stein . 2017 . Extending search phases in the Micali-Vazirani algorithm . In Proceedings of the 16th International Symposium on Experimental Algorithms (SEA\u201917) (LIPIcs), Vol. 75 . Schloss Dagstuhl\u2013Leibniz-Zentrum fuer Informatik, 10:1\u201310:19. Michael Huang and Clifford Stein. 2017. Extending search phases in the Micali-Vazirani algorithm. In Proceedings of the 16th International Symposium on Experimental Algorithms (SEA\u201917) (LIPIcs), Vol. 75. Schloss Dagstuhl\u2013Leibniz-Zentrum fuer Informatik, 10:1\u201310:19."},{"key":"e_1_2_1_22_1","volume-title":"Proceedings of the 35th International Symposium on Theoretical Aspects of Computer Science (STACS\u201918)","volume":"96","author":"Iwata Yoichi","year":"2018","unstructured":"Yoichi Iwata , Tomoaki Ogasawara , and Naoto Ohsaka . 2018 . On the power of tree-depth for fully polynomial FPT algorithms . In Proceedings of the 35th International Symposium on Theoretical Aspects of Computer Science (STACS\u201918) (LIPIcs), Vol. 96 . Schloss Dagstuhl\u2013Leibniz-Zentrum fuer Informatik, 41:1\u201341:14. Yoichi Iwata, Tomoaki Ogasawara, and Naoto Ohsaka. 2018. On the power of tree-depth for fully polynomial FPT algorithms. In Proceedings of the 35th International Symposium on Theoretical Aspects of Computer Science (STACS\u201918) (LIPIcs), Vol. 96. Schloss Dagstuhl\u2013Leibniz-Zentrum fuer Informatik, 41:1\u201341:14."},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.5555\/2634074.2634201"},{"volume-title":"Proceedings of the 30th International Workshop on Graph-Theoretic Concepts in Computer Science (WG \u201904)","author":"Juedes David","key":"e_1_2_1_24_1","unstructured":"David Juedes , Benny Chor , and Michael R. Fellows . 2004. Linear kernels in linear time, or how to save k colors in O(n2) steps . In Proceedings of the 30th International Workshop on Graph-Theoretic Concepts in Computer Science (WG \u201904) (Lecture Notes in Computer Science). Springer. David Juedes, Benny Chor, and Michael R. Fellows. 2004. Linear kernels in linear time, or how to save k colors in O(n2) steps. In Proceedings of the 30th International Workshop on Graph-Theoretic Concepts in Computer Science (WG \u201904) (Lecture Notes in Computer Science). Springer."},{"volume-title":"Proceedings of the 22nd Annual IEEE Symposium on Foundations of Computer Science (FOCS\u201981)","author":"Richard","key":"e_1_2_1_25_1","unstructured":"Richard M. Karp and Michael Sipser. 1981. Maximum matchings in sparse random graphs . In Proceedings of the 22nd Annual IEEE Symposium on Foundations of Computer Science (FOCS\u201981) . IEEE, 364--375. Richard M. Karp and Michael Sipser. 1981. Maximum matchings in sparse random graphs. In Proceedings of the 22nd Annual IEEE Symposium on Foundations of Computer Science (FOCS\u201981). IEEE, 364--375."},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611976007.11"},{"volume-title":"Proceedings of the 2nd International Workshop on Algorithm Engineering (WAE\u201992)","author":"Kececioglu John D.","key":"e_1_2_1_27_1","unstructured":"John D. Kececioglu and A. Justin Pecqueur . 1998. Computing maximum-cardinality matchings in sparse general graphs . In Proceedings of the 2nd International Workshop on Algorithm Engineering (WAE\u201992) . 121--132. John D. Kececioglu and A. Justin Pecqueur. 1998. Computing maximum-cardinality matchings in sparse general graphs. In Proceedings of the 2nd International Workshop on Algorithm Engineering (WAE\u201992). 121--132."},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1007\/s12532-009-0002-8"},{"key":"e_1_2_1_29_1","volume-title":"Proceedings of the 26th Annual European Symposium on Algorithms (ESA\u201918)","volume":"112","author":"Korenwein Viatcheslav","year":"2018","unstructured":"Viatcheslav Korenwein , Andr\u00e9 Nichterlein , Rolf Niedermeier , and Philipp Zschoche . 2018 . Data reduction for maximum matching on real-world graphs: Theory and experiments . In Proceedings of the 26th Annual European Symposium on Algorithms (ESA\u201918) (LIPIcs), Vol. 112 . Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 53:1\u201353:13. Viatcheslav Korenwein, Andr\u00e9 Nichterlein, Rolf Niedermeier, and Philipp Zschoche. 2018. Data reduction for maximum matching on real-world graphs: Theory and experiments. In Proceedings of the 26th Annual European Symposium on Algorithms (ESA\u201918) (LIPIcs), Vol. 112. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 53:1\u201353:13."},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-21708-5"},{"key":"e_1_2_1_31_1","volume-title":"Proceedings of the 26th Annual European Symposium on Algorithms (ESA\u201918)","volume":"112","author":"Kratsch Stefan","year":"2018","unstructured":"Stefan Kratsch and Florian Nelles . 2018 . Efficient and adaptive parameterized algorithms on modular decompositions . In Proceedings of the 26th Annual European Symposium on Algorithms (ESA\u201918) (LIPIcs), Vol. 112 . Schloss Dagstuhl\u2013Leibniz-Zentrum fuer Informatik, 55:1\u201355:15. Stefan Kratsch and Florian Nelles. 2018. Efficient and adaptive parameterized algorithms on modular decompositions. In Proceedings of the 26th Annual European Symposium on Algorithms (ESA\u201918) (LIPIcs), Vol. 112. Schloss Dagstuhl\u2013Leibniz-Zentrum fuer Informatik, 55:1\u201355:15."},{"key":"e_1_2_1_32_1","unstructured":"Jure Leskovec and Andrej Krevl. 2014. SNAP Datasets: Stanford Large Network Dataset Collection.  Jure Leskovec and Andrej Krevl. 2014. SNAP Datasets: Stanford Large Network Dataset Collection."},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-020-00736-0"},{"volume-title":"Proceedings of the 21st Annual IEEE Symposium on Foundations of Computer Science (FOCS\u201980)","author":"Micali Silvio","key":"e_1_2_1_34_1","unstructured":"Silvio Micali and Vijay V. Vazirani . 1980. An O(\u221a|V||E|) algorithm for finding maximum matching in general graphs . In Proceedings of the 21st Annual IEEE Symposium on Foundations of Computer Science (FOCS\u201980) . IEEE, 17--27. Silvio Micali and Vijay V. Vazirani. 1980. An O(\u221a|V||E|) algorithm for finding maximum matching in general graphs. In Proceedings of the 21st Annual IEEE Symposium on Foundations of Computer Science (FOCS\u201980). IEEE, 17--27."},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02579206"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01580444"},{"key":"e_1_2_1_37_1","volume-title":"Proceedings of the 27th International Symposium on Theoretical Aspects of Computer Science (STACS\u201907)","volume":"5","author":"Niedermeier Rolf","year":"2010","unstructured":"Rolf Niedermeier . 2010 . Reflections on multivariate algorithmics and problem parameterization . In Proceedings of the 27th International Symposium on Theoretical Aspects of Computer Science (STACS\u201907) (LIPIcs), Vol. 5 . IBFI Dagstuhl, Germany, 17--32. Rolf Niedermeier. 2010. Reflections on multivariate algorithmics and problem parameterization. In Proceedings of the 27th International Symposium on Theoretical Aspects of Computer Science (STACS\u201907) (LIPIcs), Vol. 5. IBFI Dagstuhl, Germany, 17--32."},{"key":"e_1_2_1_38_1","volume-title":"A proof of the MV matching algorithm. CoRR abs\/2012.03582","author":"Vazirani Vijay V.","year":"2020","unstructured":"Vijay V. Vazirani . 2020. A proof of the MV matching algorithm. CoRR abs\/2012.03582 ( 2020 ). arxiv:2012.03582 https:\/\/arxiv.org\/abs\/2012.03582 Vijay V. Vazirani. 2020. A proof of the MV matching algorithm. CoRR abs\/2012.03582 (2020). arxiv:2012.03582 https:\/\/arxiv.org\/abs\/2012.03582"}],"container-title":["ACM Journal of Experimental Algorithmics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3439801","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3439801","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T22:01:52Z","timestamp":1750197712000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3439801"}},"subtitle":["Theory and Experiments"],"short-title":[],"issued":{"date-parts":[[2021,4,23]]},"references-count":38,"alternative-id":["10.1145\/3439801"],"URL":"https:\/\/doi.org\/10.1145\/3439801","relation":{},"ISSN":["1084-6654","1084-6654"],"issn-type":[{"type":"print","value":"1084-6654"},{"type":"electronic","value":"1084-6654"}],"subject":[],"published":{"date-parts":[[2021,4,23]]}}}