{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,29]],"date-time":"2025-03-29T04:16:14Z","timestamp":1743221774145,"version":"3.40.3"},"publisher-location":"Berlin, Heidelberg","reference-count":21,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642308499"},{"type":"electronic","value":"9783642308505"}],"license":[{"start":{"date-parts":[[2012,1,1]],"date-time":"2012-01-01T00:00:00Z","timestamp":1325376000000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2012]]},"DOI":"10.1007\/978-3-642-30850-5_14","type":"book-chapter","created":{"date-parts":[[2012,5,28]],"date-time":"2012-05-28T01:44:33Z","timestamp":1338169473000},"page":"148-159","source":"Crossref","is-referenced-by-count":1,"title":["A More Reliable Greedy Heuristic for Maximum Matchings in Sparse Random Graphs"],"prefix":"10.1007","author":[{"given":"Martin","family":"Dietzfelbinger","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Hendrik","family":"Peilke","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Michael","family":"Rink","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"14_CR1","unstructured":"Boost C++ Libraries (version 1.44.0), http:\/\/www.boost.org\/"},{"issue":"2","key":"14_CR2","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 Struct. Algorithms\u00a012(2), 111\u2013177 (1998)","journal-title":"Random Struct. Algorithms"},{"issue":"1","key":"14_CR3","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 Comput. Syst.\u00a039(1), 3\u201314 (2006)","journal-title":"Theory Comput. Syst."},{"issue":"5","key":"14_CR4","doi-asserted-by":"publisher","first-page":"721","DOI":"10.1017\/S0963548311000265","volume":"20","author":"T. Bohman","year":"2011","unstructured":"Bohman, T., Frieze, A.M.: Karp-Sipser on Random Graphs with a Fixed Degree Sequence. Combinatorics, Probability & Computing\u00a020(5), 721\u2013741 (2011)","journal-title":"Combinatorics, Probability & Computing"},{"key":"14_CR5","first-page":"1102","volume":"arXiv","author":"C. Bordenave","year":"2011","unstructured":"Bordenave, C., Lelarge, M., Salez, J.: Matchings on infinite graphs. CoRR arXiv:1102.0712 (2011)","journal-title":"CoRR"},{"key":"14_CR6","unstructured":"Cain, J.A., Sanders, P., Wormald, N.C.: The Random Graph Threshold for k-orientiability and a Fast Algorithm for Optimal Multiple-Choice Allocation. In: Proc. 18th SODA, pp. 469\u2013476. ACM-SIAM (2007)"},{"key":"14_CR7","doi-asserted-by":"crossref","unstructured":"Chebolu, P., Frieze, A.M., Melsted, P.: Finding a Maximum Matching in a Sparse Random Graph in O(n) Expected Time. J. ACM\u00a057(4) (2010)","DOI":"10.1145\/1734213.1734218"},{"issue":"3","key":"14_CR8","doi-asserted-by":"publisher","first-page":"251","DOI":"10.1016\/S0747-7171(08)80013-2","volume":"9","author":"D. Coppersmith","year":"1990","unstructured":"Coppersmith, D., Winograd, S.: Matrix Multiplication via Arithmetic Progressions. J. Symb. Comput.\u00a09(3), 251\u2013280 (1990)","journal-title":"J. Symb. Comput."},{"key":"14_CR9","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"213","DOI":"10.1007\/978-3-642-14165-2_19","volume-title":"Automata, Languages and Programming","author":"M. Dietzfelbinger","year":"2010","unstructured":"Dietzfelbinger, M., Goerdt, A., Mitzenmacher, M., Montanari, A., Pagh, R., Rink, M.: Tight Thresholds for Cuckoo Hashing via XORSAT. In: Abramsky, S., Gavoille, C., Kirchner, C., Meyer auf der Heide, F., Spirakis, P.G. (eds.) ICALP 2010, Part I. LNCS, vol.\u00a06198, pp. 213\u2013225. Springer, Heidelberg (2010)"},{"key":"14_CR10","doi-asserted-by":"crossref","unstructured":"Dietzfelbinger, M., Peilke, H., Rink, M.: A More Reliable Greedy Heuristic for Maximum Matchings in Sparse Random Graphs. CoRR arXiv:1203.4117 (2012)","DOI":"10.1007\/978-3-642-30850-5_14"},{"key":"14_CR11","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_CR12","unstructured":"Galassi, M., Davies, J., Theiler, J., Gough, B., Jungman, G., Alken, P., Booth, M., Rossi, F.: GNU Scientific Library Reference Manual - Edition 1.15, for GSL Version 1.15 (2011), http:\/\/www.gnu.org\/software\/gsl\/manual\/"},{"issue":"4","key":"14_CR13","doi-asserted-by":"publisher","first-page":"225","DOI":"10.1137\/0202019","volume":"2","author":"J.E. Hopcroft","year":"1973","unstructured":"Hopcroft, J.E., Karp, R.M.: An n 5\/2 Algorithm for Maximum Matchings in Bipartite Graphs. SIAM J. Comput.\u00a02(4), 225\u2013231 (1973)","journal-title":"SIAM J. Comput."},{"key":"14_CR14","doi-asserted-by":"crossref","unstructured":"Karp, R.M., Sipser, M.: Maximum Matchings in Sparse Random Graphs. In: Proc. 22nd FOCS, pp. 364\u2013375. IEEE Computer Society (1981)","DOI":"10.1109\/SFCS.1981.21"},{"key":"14_CR15","doi-asserted-by":"publisher","first-page":"6","DOI":"10.1145\/297096.297131","volume":"3","author":"J. Magun","year":"1998","unstructured":"Magun, J.: Greedy Matching Algorithms: An Experimental Study. ACM Journal of Experimental Algorithmics\u00a03, 6 (1998)","journal-title":"ACM Journal of Experimental Algorithmics"},{"key":"14_CR16","doi-asserted-by":"crossref","unstructured":"Micali, S., Vazirani, V.V.: An $O(\\sqrt{|v|} \\cdot |E|)$ Algorithm for Finding Maximum Matching in General Graphs. In: Proc. 21st FOCS, pp. 17\u201327. IEEE Computer Society (1980)","DOI":"10.1109\/SFCS.1980.12"},{"key":"14_CR17","doi-asserted-by":"crossref","unstructured":"Mucha, M., Sankowski, P.: Maximum Matchings via Gaussian Elimination. In: Proc. 45th FOCS, pp. 248\u2013255. IEEE Computer Society (2004)","DOI":"10.1109\/FOCS.2004.40"},{"key":"14_CR18","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"82","DOI":"10.1007\/978-3-540-24618-3_8","volume-title":"SOFSEM 2004: Theory and Practice of Computer Science","author":"P. Sanders","year":"2004","unstructured":"Sanders, P.: Algorithms for Scalable Storage Servers. In: Van Emde Boas, P., Pokorn\u00fd, J., Bielikov\u00e1, M., \u0160tuller, J. (eds.) SOFSEM 2004. LNCS, vol.\u00a02932, pp. 82\u2013101. Springer, Heidelberg (2004)"},{"key":"14_CR19","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611970265","volume-title":"Data Structures and Network Algorithms","author":"R.E. Tarjan","year":"1983","unstructured":"Tarjan, R.E.: Data Structures and Network Algorithms. SIAM, Philadelphia (1983)"},{"key":"14_CR20","doi-asserted-by":"crossref","unstructured":"Thomas, D.B., Luk, W., Leong, P.H., Villasenor, J.D.: Gaussian Random Number Generators. ACM Comput. Surv.\u00a039 (2007)","DOI":"10.1145\/1287620.1287622"},{"issue":"1","key":"14_CR21","doi-asserted-by":"publisher","first-page":"71","DOI":"10.1007\/BF01305952","volume":"14","author":"V.V. Vazirani","year":"1994","unstructured":"Vazirani, V.V.: A Theory of Alternating Paths and Blossoms for Proving Correctness of the $O(\\sqrt{V} E)$ General Graph Maximum Matching Algorithm. Combinatorica\u00a014(1), 71\u2013109 (1994)","journal-title":"Combinatorica"}],"container-title":["Lecture Notes in Computer Science","Experimental Algorithms"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-30850-5_14","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,3,28]],"date-time":"2025-03-28T22:44:21Z","timestamp":1743201861000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-30850-5_14"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2012]]},"ISBN":["9783642308499","9783642308505"],"references-count":21,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-30850-5_14","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2012]]}}}