{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,10]],"date-time":"2025-10-10T12:42:34Z","timestamp":1760100154025},"reference-count":25,"publisher":"Cambridge University Press (CUP)","issue":"1","license":[{"start":{"date-parts":[[2009,6,22]],"date-time":"2009-06-22T00:00:00Z","timestamp":1245628800000},"content-version":"unspecified","delay-in-days":0,"URL":"https:\/\/www.cambridge.org\/core\/terms"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Combinator. Probab. Comp."],"published-print":{"date-parts":[[2010,1]]},"abstract":"<jats:p>We derive new results for the performance of a simple greedy algorithm for finding large independent sets and matchings in constant-degree regular graphs. We show that for<jats:italic>r<\/jats:italic>-regular graphs with<jats:italic>n<\/jats:italic>nodes and girth at least<jats:italic>g<\/jats:italic>, the algorithm finds an independent set of expected cardinality<jats:disp-formula><jats:graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"gif\" mimetype=\"image\" position=\"float\" xlink:type=\"simple\" xlink:href=\"S0963548309990186_eqnU1\" \/><\/jats:disp-formula>where<jats:italic>f<\/jats:italic>(<jats:italic>r<\/jats:italic>) is a function which we explicitly compute. A similar result is established for matchings. Our results imply improved bounds for the size of the largest independent set in these graphs, and provide the first results of this type for matchings. As an implication we show that the greedy algorithm returns a nearly perfect matching when both the degree<jats:italic>r<\/jats:italic>and girth<jats:italic>g<\/jats:italic>are large. Furthermore, we show that the cardinality of independent sets and matchings produced by the greedy algorithm in<jats:italic>arbitrary<\/jats:italic>bounded-degree graphs is concentrated around the mean. Finally, we analyse the performance of the greedy algorithm for the case of random i.i.d. weighted independent sets and matchings, and obtain a remarkably simple expression for the limiting expected values produced by the algorithm. In fact, all the other results are obtained as straightforward corollaries from the results for the weighted case.<\/jats:p>","DOI":"10.1017\/s0963548309990186","type":"journal-article","created":{"date-parts":[[2009,6,22]],"date-time":"2009-06-22T10:00:36Z","timestamp":1245664836000},"page":"61-85","source":"Crossref","is-referenced-by-count":22,"title":["Randomized Greedy Algorithms for Independent Sets and Matchings in Regular Graphs: Exact Results and Finite Girth Corrections"],"prefix":"10.1017","volume":"19","author":[{"given":"DAVID","family":"GAMARNIK","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"DAVID A.","family":"GOLDBERG","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"56","published-online":{"date-parts":[[2009,6,22]]},"reference":[{"key":"S0963548309990186_ref23","doi-asserted-by":"publisher","DOI":"10.1016\/0012-365X(83)90273-X"},{"key":"S0963548309990186_ref25","doi-asserted-by":"crossref","first-page":"#2","DOI":"10.37236\/1221","article-title":"The independence number of dense graphs with large odd girth","volume":"2","author":"Shearer","year":"1995","journal-title":"Electron. J. Combin."},{"key":"S0963548309990186_ref18","doi-asserted-by":"publisher","DOI":"10.1016\/j.jctb.2007.02.006"},{"key":"S0963548309990186_ref15","first-page":"475","article-title":"Improved approximations of bounded-degree independent sets via subgraph removal","volume":"1","author":"Halld\u00f3rsson","year":"1994","journal-title":"Nordic J. Comput."},{"key":"S0963548309990186_ref14","doi-asserted-by":"publisher","DOI":"10.1016\/0097-3165(83)90003-1"},{"key":"S0963548309990186_ref3","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.1015"},{"key":"S0963548309990186_ref8","volume-title":"Probability: Theory and Examples","author":"Durrett","year":"1996"},{"key":"S0963548309990186_ref9","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.3240020104"},{"key":"S0963548309990186_ref11","unstructured":"[11] Frieze A. Personal communication."},{"key":"S0963548309990186_ref21","doi-asserted-by":"publisher","DOI":"10.1016\/0166-218X(92)90041-8"},{"key":"S0963548309990186_ref1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02579451"},{"key":"S0963548309990186_ref20","doi-asserted-by":"publisher","DOI":"10.1007\/BF00290149"},{"key":"S0963548309990186_ref2","doi-asserted-by":"publisher","DOI":"10.1016\/0097-3165(80)90030-8"},{"key":"S0963548309990186_ref5","first-page":"365","volume-title":"Proc. 5th Annual ACM\u2013SIAM Symposium on Discrete Algorithms","author":"Berman","year":"1994"},{"key":"S0963548309990186_ref7","doi-asserted-by":"crossref","first-page":"#9","DOI":"10.37236\/1189","article-title":"The independence number of graphs with large odd girth","volume":"1","author":"Denley","year":"1994","journal-title":"Electron. J. Combin."},{"key":"S0963548309990186_ref10","doi-asserted-by":"crossref","first-page":"#1","DOI":"10.37236\/1002","article-title":"Maximum matchings in regular graphs of high girth","volume":"14","author":"Flaxman","year":"2007","journal-title":"Electron. J. Combin."},{"key":"S0963548309990186_ref12","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.20072"},{"key":"S0963548309990186_ref4","first-page":"1","volume-title":"Discrete Combinatorial Probability","author":"Aldous","year":"2003"},{"key":"S0963548309990186_ref22","first-page":"163","volume-title":"Research Trends in Combinatorial Optimization","author":"Rautenbach","year":"2008"},{"key":"S0963548309990186_ref13","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(76)90059-1"},{"key":"S0963548309990186_ref16","doi-asserted-by":"publisher","DOI":"10.1007\/BF02523693"},{"key":"S0963548309990186_ref6","doi-asserted-by":"publisher","DOI":"10.1016\/S0195-6698(80)80030-8"},{"key":"S0963548309990186_ref17","doi-asserted-by":"publisher","DOI":"10.4153\/CMB-1982-024-9"},{"key":"S0963548309990186_ref19","doi-asserted-by":"publisher","DOI":"10.1002\/(SICI)1098-2418(199705)10:3<353::AID-RSA5>3.0.CO;2-V"},{"key":"S0963548309990186_ref24","doi-asserted-by":"publisher","DOI":"10.1016\/0095-8956(91)90080-4"}],"container-title":["Combinatorics, Probability and Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.cambridge.org\/core\/services\/aop-cambridge-core\/content\/view\/S0963548309990186","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,5,19]],"date-time":"2020-05-19T23:02:35Z","timestamp":1589929355000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.cambridge.org\/core\/product\/identifier\/S0963548309990186\/type\/journal_article"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2009,6,22]]},"references-count":25,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2010,1]]}},"alternative-id":["S0963548309990186"],"URL":"https:\/\/doi.org\/10.1017\/s0963548309990186","relation":{},"ISSN":["0963-5483","1469-2163"],"issn-type":[{"value":"0963-5483","type":"print"},{"value":"1469-2163","type":"electronic"}],"subject":[],"published":{"date-parts":[[2009,6,22]]}}}