{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,26]],"date-time":"2025-03-26T09:34:04Z","timestamp":1742981644575,"version":"3.40.3"},"publisher-location":"Berlin, Heidelberg","reference-count":7,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540705741"},{"type":"electronic","value":"9783540705758"}],"license":[{"start":{"date-parts":[[2008,1,1]],"date-time":"2008-01-01T00:00:00Z","timestamp":1199145600000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2008]]},"DOI":"10.1007\/978-3-540-70575-8_14","type":"book-chapter","created":{"date-parts":[[2008,8,12]],"date-time":"2008-08-12T16:07:43Z","timestamp":1218557263000},"page":"161-172","source":"Crossref","is-referenced-by-count":1,"title":["Finding a Maximum Matching in a Sparse Random Graph in O(n) Expected Time"],"prefix":"10.1007","author":[{"given":"Prasad","family":"Chebolu","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Alan","family":"Frieze","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"P\u00e1ll","family":"Melsted","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"14_CR1","doi-asserted-by":"publisher","first-page":"111","DOI":"10.1002\/(SICI)1098-2418(199803)12:2<111::AID-RSA1>3.0.CO;2-#","volume":"12","author":"J. Aronson","year":"1998","unstructured":"Aronson, J., Frieze, A.M., Pittel, B.: Maximum matchings in sparse random graphs: Karp-Sipser revisited. Random Structures and Algorithms\u00a012, 111\u2013177 (1998)","journal-title":"Random Structures and Algorithms"},{"key":"14_CR2","doi-asserted-by":"publisher","first-page":"3","DOI":"10.1007\/s00224-005-1254-y","volume":"39","author":"H. Bast","year":"2006","unstructured":"Bast, H., Mehlhorn, K., Sch\u00e4fer, G., Tamaki, H.: Matching Algorithms are Fast in Sparse Random Graphs. Theory of Computing Systems\u00a039, 3\u201314 (2006)","journal-title":"Theory of Computing Systems"},{"key":"14_CR3","doi-asserted-by":"publisher","first-page":"449","DOI":"10.4153\/CJM-1965-045-4","volume":"17","author":"J. Edmonds","year":"1965","unstructured":"Edmonds, J.: Paths, Trees and Flowers. Canadian Journal of Mathematics\u00a017, 449\u2013467 (1965)","journal-title":"Canadian Journal of Mathematics"},{"key":"14_CR4","first-page":"95","volume-title":"Trends in Mathematics","author":"A.M. Frieze","year":"2004","unstructured":"Frieze, A.M., Pittel, B.: Perfect matchings in random graphs with prescribed minimal degree. In: Trends in Mathematics, pp. 95\u2013132. Birkhauser Verlag, Basel (2004)"},{"key":"14_CR5","doi-asserted-by":"crossref","unstructured":"Karp, R.M., Sipser, M.: Maximum Matchings in Sparse Random Graphs. In: Proceedings of the 22nd Annual IEEE Symposium on Foundations of Computer Science, pp. 364\u2013375 (1981)","DOI":"10.1109\/SFCS.1981.21"},{"key":"14_CR6","doi-asserted-by":"crossref","unstructured":"Micali, S., Vazirani, V.V.: An $O(\\sqrt{V}E)$ Algorithm for Finding Maximum Matching in General Graphs. In: Proceedings of the 21st Annual IEEE Symposium on Foundations of Computer Science, pp. 17\u201327 (1980)","DOI":"10.1109\/SFCS.1980.12"},{"key":"14_CR7","doi-asserted-by":"publisher","first-page":"1329","DOI":"10.1145\/195613.195663","volume":"41","author":"R. Motwani","year":"1994","unstructured":"Motwani, R.: Average-case Analysis of Algorithms for Matchings and Related Problems. Journal of the ACM\u00a041, 1329\u20131356 (1994)","journal-title":"Journal of the ACM"}],"container-title":["Lecture Notes in Computer Science","Automata, Languages and Programming"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-540-70575-8_14","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,5,2]],"date-time":"2024-05-02T03:24:51Z","timestamp":1714620291000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-540-70575-8_14"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2008]]},"ISBN":["9783540705741","9783540705758"],"references-count":7,"URL":"https:\/\/doi.org\/10.1007\/978-3-540-70575-8_14","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2008]]}}}