{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,18]],"date-time":"2026-01-18T08:19:14Z","timestamp":1768724354147,"version":"3.49.0"},"reference-count":4,"publisher":"Wiley","issue":"1","license":[{"start":{"date-parts":[[2007,7,5]],"date-time":"2007-07-05T00:00:00Z","timestamp":1183593600000},"content-version":"vor","delay-in-days":5970,"URL":"http:\/\/onlinelibrary.wiley.com\/termsAndConditions#vor"}],"funder":[{"DOI":"10.13039\/100004415","name":"NATO","doi-asserted-by":"crossref","award":["RG0088\/89"],"award-info":[{"award-number":["RG0088\/89"]}],"id":[{"id":"10.13039\/100004415","id-type":"DOI","asserted-by":"crossref"}]},{"DOI":"10.13039\/100004415","name":"NATO","doi-asserted-by":"crossref","award":["RG0088\/89"],"award-info":[{"award-number":["RG0088\/89"]}],"id":[{"id":"10.13039\/100004415","id-type":"DOI","asserted-by":"crossref"}]},{"name":"NSF","award":["CCR-8900112"],"award-info":[{"award-number":["CCR-8900112"]}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Random Struct Algorithms"],"published-print":{"date-parts":[[1991,3]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>We consider a randomized version of the greedy algorithm for finding a large matching in a graph. We assume that the next edge is always randomly chosen from those remaining. We analyze the performance of this algorithm when the input graph is fixed. We show that there are graphs for which this Randomized Greedy Algorithm <jats:italic>(RGA)<\/jats:italic> usually only obtains a matching close in size to that guaranteed by worst\u2010case analysis (i.e., half the size of the maximum). For some classes of sparse graphs (e.g., planar graphs and forests) we show that the <jats:italic>RGA<\/jats:italic> performs significantly better than the worst\u2010case. Our main theorem concerns forests. We prove that the ratio to maximum here is at least 0.7690\u2026, and that this bound is tight.<\/jats:p>","DOI":"10.1002\/rsa.3240020104","type":"journal-article","created":{"date-parts":[[2010,7,12]],"date-time":"2010-07-12T04:55:08Z","timestamp":1278910508000},"page":"29-45","source":"Crossref","is-referenced-by-count":30,"title":["Randomized greedy matching"],"prefix":"10.1002","volume":"2","author":[{"given":"Martin","family":"Dyer","sequence":"first","affiliation":[]},{"given":"Alan","family":"Frieze","sequence":"additional","affiliation":[]}],"member":"311","published-online":{"date-parts":[[2007,7,5]]},"reference":[{"key":"e_1_2_1_1_2","first-page":"113","article-title":"Martingales, isoperimetric inequalities and random graphs","volume":"52","author":"Bollob\u00e1s B.","year":"1987","journal-title":"Coll. Math. Soc. J. Bolyai"},{"key":"e_1_2_1_2_2","first-page":"240","volume-title":"On the complexity of a generalised matching problem, Proceedings of the 10th Annual ACM Symposium on Theory of Computing","author":"Kirkpatrick D. G.","year":"1978"},{"key":"e_1_2_1_3_2","doi-asserted-by":"crossref","unstructured":"B.KorteandD.Hausmann An analysis of the greedy algorithm for independence systems in Algorithmic Aspects of Combinatorics B. Alspach. P. Hall and D. J. Miller Eds. Annals of Discrete Mathematics2 65\u201374(1978).","DOI":"10.1016\/S0167-5060(08)70322-4"},{"key":"e_1_2_1_4_2","doi-asserted-by":"crossref","unstructured":"C. J. H.McDiarmid On the method of bounded difference inSurveys in Combinatorics Proceedings of the Twelfth British Combinatorial ConferenceJ. Siemons Ed. 1989 pp.148\u2013188.","DOI":"10.1017\/CBO9781107359949.008"}],"container-title":["Random Structures &amp; Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/api.wiley.com\/onlinelibrary\/tdm\/v1\/articles\/10.1002%2Frsa.3240020104","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/api.wiley.com\/onlinelibrary\/tdm\/v1\/articles\/10.1002%2Frsa.3240020104","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/pdf\/10.1002\/rsa.3240020104","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,10,23]],"date-time":"2023-10-23T06:13:58Z","timestamp":1698041638000},"score":1,"resource":{"primary":{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/10.1002\/rsa.3240020104"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1991,3]]},"references-count":4,"journal-issue":{"issue":"1","published-print":{"date-parts":[[1991,3]]}},"alternative-id":["10.1002\/rsa.3240020104"],"URL":"https:\/\/doi.org\/10.1002\/rsa.3240020104","archive":["Portico"],"relation":{},"ISSN":["1042-9832","1098-2418"],"issn-type":[{"value":"1042-9832","type":"print"},{"value":"1098-2418","type":"electronic"}],"subject":[],"published":{"date-parts":[[1991,3]]}}}