{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2023,1,9]],"date-time":"2023-01-09T21:29:59Z","timestamp":1673299799567},"reference-count":17,"publisher":"Association for Computing Machinery (ACM)","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["ACM J. Exp. Algorithmics"],"published-print":{"date-parts":[[1998,9]]},"abstract":"We conduct an experimental study of several greedy algorithms for finding large matchings in graphs. Further we propose a new graph reduction, called <i>k<\/i>-Block Reduction, and present two novel algorithms using extra heuristics in the matching step and <i>k<\/i>-Block Reduction for <i>k<\/i> = 3. Greedy matching algorithms can be used for finding a good approximation of the maximum matching in a graph <i>G<\/i> if no exact solution is required, or as a fast preprocessing step to some other matching algorithm. The studied greedy algorithms run in <i>O(m)<\/i>. They are easy to implement and their correctness and their running time are simple to prove. Our experiments show that a good greedy algorithm looses on average at most one edge on random graphs from <i>G<inf>n,p<\/inf><\/i> with up to 10,000 vertices. Furthermore the experiments show for which edge densities in random graphs the maximum matching problem is difficult to solve.<\/jats:p>","DOI":"10.1145\/297096.297131","type":"journal-article","created":{"date-parts":[[2005,8,2]],"date-time":"2005-08-02T06:34:09Z","timestamp":1122964449000},"page":"6","source":"Crossref","is-referenced-by-count":19,"title":["Greeding matching algorithms, an experimental study"],"prefix":"10.1145","volume":"3","author":[{"given":"Jakob","family":"Magun","sequence":"first","affiliation":[{"name":"Swiss Federal Institute of Technology, Z\u00fcrich"}]}],"member":"320","published-online":{"date-parts":[[1998,9]]},"reference":[{"key":"e_1_2_2_1_1","doi-asserted-by":"crossref","unstructured":"ARONSON J. FRIEZE A. M. AND PITTEL B. G. 1997. Maximum matchings in sparse random graphs: Karp-sipser re-visited preprint. ARONSON J. FRIEZE A. M. AND PITTEL B. G. 1997. Maximum matchings in sparse random graphs: Karp-sipser re-visited preprint.","DOI":"10.1002\/(SICI)1098-2418(199803)12:2<111::AID-RSA1>3.0.CO;2-#"},{"key":"e_1_2_2_2_1","first-page":"519","volume-title":"DIMACS Series in Discrete mathematics and Theoretical Computer Science 1","author":"CROCKER S. T.","unstructured":"CROCKER , S. T. 1993. An experimental comparison of two maximum cardinality matching programs. Network Flows and Matching , DIMACS Series in Discrete mathematics and Theoretical Computer Science 1 , 519 - 537 . CROCKER, S. T. 1993. An experimental comparison of two maximum cardinality matching programs. Network Flows and Matching, DIMACS Series in Discrete mathematics and Theoretical Computer Science 1, 519-537."},{"key":"e_1_2_2_3_1","doi-asserted-by":"publisher","DOI":"10.1214\/aoap\/1177005436"},{"key":"e_1_2_2_4_1","doi-asserted-by":"publisher","DOI":"10.4153\/CJM-1965-045-4"},{"key":"e_1_2_2_5_1","unstructured":"FRIEZE A. M. RADCLIFFE A. J. AND \n SUEN S.\n 1993.\n Analysis of a simple greedy matching algorithm on cubic random graphs\n . Volume \n 4\n of \n Proc\n . Fourth. \n Annual ACM-SIAM Symposium\n on Discrete Algorithms (\n 1993\n ) pp. \n 341\n -\n 351\n . FRIEZE A. M. RADCLIFFE A. J. AND SUEN S. 1993. Analysis of a simple greedy matching algorithm on cubic random graphs. Volume 4 of Proc. Fourth. Annual ACM-SIAM Symposium on Discrete Algorithms (1993) pp. 341-351."},{"key":"e_1_2_2_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/321941.321942"},{"key":"e_1_2_2_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/800061.808753"},{"key":"e_1_2_2_8_1","doi-asserted-by":"publisher","DOI":"10.1137\/0403006"},{"key":"e_1_2_2_9_1","doi-asserted-by":"publisher","DOI":"10.1112\/jlms\/s1-10.37.26"},{"key":"e_1_2_2_10_1","first-page":"364","volume-title":"IEEE Symp. Foundations of Computer Science (Nashville","author":"KARP R. M.","year":"1981","unstructured":"KARP , R. M. AND SIPSER , M. 1981 . Maximum matchings in sparse random graphs. Volume 22 of Proc. of the Ann . IEEE Symp. Foundations of Computer Science (Nashville , 1981), pp. 364 - 375 . KARP, R. M. AND SIPSER, M. 1981. Maximum matchings in sparse random graphs. Volume 22 of Proc. of the Ann. IEEE Symp. Foundations of Computer Science (Nashville, 1981), pp. 364-375."},{"key":"e_1_2_2_11_1","volume-title":"Combinatorial Optimization: Networks and Matroids. Holt, Reinehart and Winston","author":"LAWLER E. L.","year":"1976","unstructured":"LAWLER , E. L. 1976 . Combinatorial Optimization: Networks and Matroids. Holt, Reinehart and Winston , New York . LAWLER, E. L. 1976. Combinatorial Optimization: Networks and Matroids. Holt, Reinehart and Winston, New York."},{"key":"e_1_2_2_12_1","first-page":"539","volume-title":"DIMACS Series in Discrete mathematics and Theoretical Computer Science 1","author":"MATTINGLY B.","unstructured":"MATTINGLY , B. AND RITCHEY , N. P. 1993. Implementing an O(\u221aNM) cardinality matching algorithm. Network Flows and Matching , DIMACS Series in Discrete mathematics and Theoretical Computer Science 1 , 539 - 556 . MATTINGLY, B. AND RITCHEY, N. P. 1993. Implementing an O(\u221aNM) cardinality matching algorithm. Network Flows and Matching, DIMACS Series in Discrete mathematics and Theoretical Computer Science 1, 539-556."},{"key":"e_1_2_2_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/204865.204889"},{"key":"e_1_2_2_14_1","unstructured":"MEHLHORN K. N\u00c4HER S. AND UHRIG S. 1996. Leda version 3.4-R source code module _mc_matching.cc. MEHLHORN K. N\u00c4HER S. AND UHRIG S. 1996. Leda version 3.4-R source code module _mc_matching.cc."},{"key":"e_1_2_2_15_1","first-page":"17","volume-title":"IEEE Symp. Foundations of Computer Science (Syracuse","author":"MICALI S.","year":"1980","unstructured":"MICALI , S. AND VAZIRANI , V. 1980 . An O(\u221aVE) algorithm for finding maximum matching in general graphs. Volume 21 of Proc. of the Ann . IEEE Symp. Foundations of Computer Science (Syracuse , 1980), pp. 17 - 25 . MICALI, S. AND VAZIRANI, V. 1980. An O(\u221aVE) algorithm for finding maximum matching in general graphs. Volume 21 of Proc. of the Ann. IEEE Symp. Foundations of Computer Science (Syracuse, 1980), pp. 17-25."},{"key":"e_1_2_2_16_1","doi-asserted-by":"publisher","DOI":"10.5555\/3485"},{"key":"e_1_2_2_17_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01874391"}],"container-title":["ACM Journal of Experimental Algorithmics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/297096.297131","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,12,31]],"date-time":"2022-12-31T10:42:11Z","timestamp":1672483331000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/297096.297131"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1998,9]]},"references-count":17,"alternative-id":["10.1145\/297096.297131"],"URL":"http:\/\/dx.doi.org\/10.1145\/297096.297131","relation":{},"ISSN":["1084-6654","1084-6654"],"issn-type":[{"value":"1084-6654","type":"print"},{"value":"1084-6654","type":"electronic"}],"subject":["Theoretical Computer Science"],"published":{"date-parts":[[1998,9]]}}}