{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,4,24]],"date-time":"2024-04-24T19:59:05Z","timestamp":1713988745263},"reference-count":8,"publisher":"Cambridge University Press (CUP)","issue":"1","license":[{"start":{"date-parts":[[2008,9,12]],"date-time":"2008-09-12T00:00:00Z","timestamp":1221177600000},"content-version":"unspecified","delay-in-days":4944,"URL":"https:\/\/www.cambridge.org\/core\/terms"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Combinator. Probab. Comp."],"published-print":{"date-parts":[[1995,3]]},"abstract":"<jats:p>We consider the performance of a simple greedy matching algorithm MINGREEDY when applied to random cubic graphs. We show that if \u03bb<jats:sub>n<\/jats:sub> is the expected number of vertices not matched by MINGREEDY, there are positive constants <jats:italic>c<\/jats:italic><jats:sub>1<\/jats:sub> and <jats:italic>c<\/jats:italic><jats:sub>2<\/jats:sub> such that <jats:italic>C<\/jats:italic><jats:sub>1<\/jats:sub><jats:italic>n<\/jats:italic><jats:sup>1\/5<\/jats:sup> \u2264 <jats:italic>\u03bb<jats:sub>n<\/jats:sub><\/jats:italic> \u2264 <jats:italic>C<\/jats:italic><jats:sub>2<\/jats:sub><jats:italic>n<\/jats:italic><jats:sup>1\/5<\/jats:sup> log <jats:italic>n<\/jats:italic>.<\/jats:p>","DOI":"10.1017\/s0963548300001474","type":"journal-article","created":{"date-parts":[[2008,9,12]],"date-time":"2008-09-12T07:15:47Z","timestamp":1221203747000},"page":"47-66","source":"Crossref","is-referenced-by-count":6,"title":["Analysis of a Simple Greedy Matching Algorithm on Random Cubic Graphs"],"prefix":"10.1017","volume":"4","author":[{"given":"Alan","family":"Frieze","sequence":"first","affiliation":[]},{"given":"A. J.","family":"Radcliffe","sequence":"additional","affiliation":[]},{"given":"Stephen","family":"Suen","sequence":"additional","affiliation":[]}],"member":"56","published-online":{"date-parts":[[2008,9,12]]},"reference":[{"key":"S0963548300001474_ref003","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.3240020104"},{"key":"S0963548300001474_ref002","doi-asserted-by":"publisher","DOI":"10.1016\/S0195-6698(80)80030-8"},{"key":"S0963548300001474_ref004","unstructured":"[4] Dyer M. E. , Frieze A. M. and Pittel B. (to appear) On the average performance of the greedy matching algorithm."},{"key":"S0963548300001474_ref001","doi-asserted-by":"publisher","DOI":"10.1016\/0097-3165(78)90059-6"},{"key":"S0963548300001474_ref008","doi-asserted-by":"publisher","DOI":"10.1007\/BF01874391"},{"key":"S0963548300001474_ref007","doi-asserted-by":"crossref","unstructured":"[7] Karp R. M. and Sipser M. (1981) Maximum matchings in sparse random graphs, Proceedings of the 22nd Annual IEEE Symposium on Foundations of Computing 364\u2013375.","DOI":"10.1109\/SFCS.1981.21"},{"key":"S0963548300001474_ref006","doi-asserted-by":"crossref","unstructured":"[6] Korte B. and Hausmann D. (1978) An analysis of the greedy algorithm for independence systems, In: Alspach B. , Hall P. and Milles D. J. (eds.) Algorithmic Aspects of Combinatorics, Annals of Discrete Mathematics, 2 65\u201374.","DOI":"10.1016\/S0167-5060(08)70322-4"},{"key":"S0963548300001474_ref005","doi-asserted-by":"publisher","DOI":"10.1137\/0403006"}],"container-title":["Combinatorics, Probability and Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.cambridge.org\/core\/services\/aop-cambridge-core\/content\/view\/S0963548300001474","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,14]],"date-time":"2019-05-14T15:22:21Z","timestamp":1557847341000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.cambridge.org\/core\/product\/identifier\/S0963548300001474\/type\/journal_article"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1995,3]]},"references-count":8,"journal-issue":{"issue":"1","published-print":{"date-parts":[[1995,3]]}},"alternative-id":["S0963548300001474"],"URL":"https:\/\/doi.org\/10.1017\/s0963548300001474","relation":{},"ISSN":["0963-5483","1469-2163"],"issn-type":[{"value":"0963-5483","type":"print"},{"value":"1469-2163","type":"electronic"}],"subject":[],"published":{"date-parts":[[1995,3]]}}}