{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,26]],"date-time":"2025-02-26T05:30:29Z","timestamp":1740547829378,"version":"3.38.0"},"publisher-location":"Berlin, Heidelberg","reference-count":13,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540212362"},{"type":"electronic","value":"9783540247494"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2004]]},"DOI":"10.1007\/978-3-540-24749-4_8","type":"book-chapter","created":{"date-parts":[[2010,9,8]],"date-time":"2010-09-08T19:01:54Z","timestamp":1283972514000},"page":"81-92","source":"Crossref","is-referenced-by-count":2,"title":["Matching Algorithms Are Fast in Sparse Random Graphs"],"prefix":"10.1007","author":[{"given":"Holger","family":"Bast","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Kurt","family":"Mehlhorn","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Guido","family":"Sch\u00e4fer","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Hisao","family":"Tamaki","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"8_CR1","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-662-04315-8","volume-title":"Proofs from THE BOOK","author":"M. Aigner","year":"2001","unstructured":"Aigner, M., Ziegler, G.M.: Proofs from THE BOOK. Springer, Heidelberg (2001)"},{"key":"8_CR2","doi-asserted-by":"crossref","unstructured":"Cherkassky, B.V., Goldberg, A.V., Martin, P., Setubal, J.C., Stolfi, J.: Augment or push: A computational study of bipartite matching and unit-capacity flow algorithms. The ACM Journal of Experimental Algorithmics\u00a03 (1998), http:\/\/www.jea.acm.org\/1998\/CherkasskyAugment","DOI":"10.1145\/297096.297140"},{"issue":"6","key":"8_CR3","doi-asserted-by":"publisher","first-page":"521","DOI":"10.1007\/BF01940880","volume":"15","author":"J. Cheriyan","year":"1996","unstructured":"Cheriyan, J., Mehlhorn, K.: Algorithms for dense graphs and networks on the random access computer. Algorithmica\u00a015(6), 521\u2013549 (1996)","journal-title":"Algorithmica"},{"issue":"b","key":"8_CR4","doi-asserted-by":"crossref","first-page":"125","DOI":"10.6028\/jres.069B.013","volume":"69","author":"J. Edmonds","year":"1965","unstructured":"Edmonds, J.: Maximum matching and a polyhedron with (0, 1) vertices. Journal of Research of the National Bureau of Standards\u00a069(b), 125\u2013130 (1965)","journal-title":"Journal of Research of the National Bureau of Standards"},{"key":"8_CR5","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":"8_CR6","doi-asserted-by":"crossref","first-page":"290","DOI":"10.5486\/PMD.1959.6.3-4.12","volume":"6","author":"P. Erd\u00f6s","year":"1959","unstructured":"Erd\u00f6s, P., R\u00e8nyi, A.: On random graphs. Publ. Math. Debrecen\u00a06, 290\u2013297 (1959)","journal-title":"Publ. Math. Debrecen"},{"issue":"2","key":"8_CR7","doi-asserted-by":"publisher","first-page":"261","DOI":"10.1006\/jcss.1995.1065","volume":"51","author":"T. Feder","year":"1995","unstructured":"Feder, T., Motwani, R.: Clique partitions, graph compression and speeding up algorithms. Journal of Computer and System Sciences (JCSS)\u00a051(2), 261\u2013272 (1995)","journal-title":"Journal of Computer and System Sciences (JCSS)"},{"key":"8_CR8","doi-asserted-by":"publisher","first-page":"221","DOI":"10.1145\/321941.321942","volume":"23","author":"H.N. Gabow","year":"1976","unstructured":"Gabow, H.N.: An efficient implementation of Edmond\u2019s algorithm for maximum matching on graphs. Journal of the ACM\u00a023, 221\u2013234 (1976)","journal-title":"Journal of the ACM"},{"key":"8_CR9","unstructured":"Gnuplot, http:\/\/www.gnuplot.info"},{"issue":"4","key":"8_CR10","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 n5\/2 algorithm for maximum matchings in bipartite graphs. SIAM Journal of Computing\u00a02(4), 225\u2013231 (1973)","journal-title":"SIAM Journal of Computing"},{"key":"8_CR11","volume-title":"LEDA: A Platform for Combinatorial and Geometric Computing","author":"K. Mehlhorn","year":"1999","unstructured":"Mehlhorn, K., N\u00e4her, S.: LEDA: A Platform for Combinatorial and Geometric Computing. Cambridge University Press, Cambridge (1999)"},{"issue":"6","key":"8_CR12","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(6), 1329\u20131356 (1994)","journal-title":"Journal of the ACM"},{"key":"8_CR13","doi-asserted-by":"crossref","unstructured":"Micali, S., Vazirani, V.: An O(|V|0.5|E|) algorithm for finding maximum matchings in general graphs. In: Foundations of Computer Science, pp. 17\u201327 (1980)","DOI":"10.1109\/SFCS.1980.12"}],"container-title":["Lecture Notes in Computer Science","STACS 2004"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-540-24749-4_8","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,2,25]],"date-time":"2025-02-25T17:08:24Z","timestamp":1740503304000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-540-24749-4_8"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2004]]},"ISBN":["9783540212362","9783540247494"],"references-count":13,"URL":"https:\/\/doi.org\/10.1007\/978-3-540-24749-4_8","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2004]]}}}