{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,14]],"date-time":"2026-05-14T04:25:59Z","timestamp":1778732759384,"version":"3.51.4"},"reference-count":13,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2012,2,24]],"date-time":"2012-02-24T00:00:00Z","timestamp":1330041600000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2013,5]]},"DOI":"10.1007\/s00453-012-9625-7","type":"journal-article","created":{"date-parts":[[2012,2,23]],"date-time":"2012-02-23T11:11:17Z","timestamp":1329995477000},"page":"87-92","source":"Crossref","is-referenced-by-count":12,"title":["Maximum Matching in Regular and Almost Regular Graphs"],"prefix":"10.1007","volume":"66","author":[{"given":"Raphael","family":"Yuster","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2012,2,24]]},"reference":[{"key":"9625_CR1","first-page":"130","volume-title":"Proceedings of the Tenth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA)","author":"T.C. Biedl","year":"1999","unstructured":"Biedl, T.C., Bose, P., Demaine, E.D., Lubiw, A.: Efficient algorithms for Petersen\u2019s matching theorem. In: Proceedings of the Tenth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp.\u00a0130\u2013139. SIAM, Philadelphia (1999)"},{"key":"9625_CR2","doi-asserted-by":"crossref","first-page":"586","DOI":"10.1007\/BFb0032060","volume-title":"Proceedings of the 17th International Colloquium on Automata, Languages and Programming (ICALP)","author":"N. Blum","year":"1990","unstructured":"Blum, N.: A new approach to maximum matching in general graphs. In: Proceedings of the 17th International Colloquium on Automata, Languages and Programming (ICALP), pp.\u00a0586\u2013597 (1990)"},{"key":"9625_CR3","volume-title":"Extremal Graph Theory","author":"B. Bollob\u00e1s","year":"1978","unstructured":"Bollob\u00e1s, B.: Extremal Graph Theory. Academic Press, San Diego (1978)"},{"issue":"1","key":"9625_CR4","doi-asserted-by":"crossref","first-page":"5","DOI":"10.1007\/s004930170002","volume":"21","author":"R. Cole","year":"2001","unstructured":"Cole, R., Ost, K., Schirra, S.: Edge-coloring bipartite multigraphs in o(elogd) time. Combinatorica 21(1), 5\u201312 (2001)","journal-title":"Combinatorica"},{"issue":"3","key":"9625_CR5","doi-asserted-by":"crossref","first-page":"449","DOI":"10.4153\/CJM-1965-045-4","volume":"17","author":"J. Edmonds","year":"1965","unstructured":"Edmonds, J.: Paths, trees, and flowers. Can. J. Math. 17(3), 449\u2013467 (1965)","journal-title":"Can. J. Math."},{"key":"9625_CR6","doi-asserted-by":"crossref","first-page":"117","DOI":"10.1137\/0211009","volume":"11","author":"H.N. Gabow","year":"1982","unstructured":"Gabow, H.N., Kariv, O.: Algorithms for edge coloring bipartite graphs and multigraphs. SIAM J. Comput. 11, 117 (1982)","journal-title":"SIAM J. Comput."},{"issue":"4","key":"9625_CR7","doi-asserted-by":"crossref","first-page":"815","DOI":"10.1145\/115234.115366","volume":"38","author":"H.N. Gabow","year":"1991","unstructured":"Gabow, H.N., Tarjan, R.E.: Faster scaling algorithms for general graph matching problems. J. ACM 38(4), 815\u2013853 (1991)","journal-title":"J. ACM"},{"key":"9625_CR8","doi-asserted-by":"crossref","first-page":"39","DOI":"10.1145\/1806689.1806697","volume-title":"Proceedings of the 42nd ACM Symposium on Theory of Computing (STOC)","author":"A. Goel","year":"2010","unstructured":"Goel, A., Kapralov, M., Khanna, S.: Perfect matchings in o(nlogn) time in regular bipartite graphs. In: Proceedings of the 42nd ACM Symposium on Theory of Computing (STOC), pp.\u00a039\u201346. ACM, New York (2010)."},{"issue":"2","key":"9625_CR9","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1145\/1721837.1721843","volume":"6","author":"A. Goel","year":"2010","unstructured":"Goel, A., Kapralov, M., Khanna, S.: Perfect matchings via uniform sampling in regular bipartite graphs. ACM Trans. Algorithms (TALG) 6(2), 1\u201313 (2010)","journal-title":"ACM Trans. Algorithms (TALG)"},{"key":"9625_CR10","doi-asserted-by":"crossref","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. 2, 225 (1973)","journal-title":"SIAM J. Comput."},{"key":"9625_CR11","first-page":"17","volume-title":"Proceedings of the 21st Annual Symposium on Foundations of Computer Science (FOCS)","author":"S. Micali","year":"1980","unstructured":"Micali, S., Vazirani, V.: An $O(\\sqrt{(}|V|) |E|)$ algorithm for finding maximum matching in general graphs. In: Proceedings of the 21st Annual Symposium on Foundations of Computer Science (FOCS), pp. 17\u201327 (1980)"},{"issue":"1","key":"9625_CR12","doi-asserted-by":"crossref","first-page":"71","DOI":"10.1007\/BF01305952","volume":"14","author":"V. Vazirani","year":"1994","unstructured":"Vazirani, V.: A theory of alternating paths and blossoms for proving correctness of the general graph maximum matching algorithm. Combinatorica 14(1), 71\u2013109 (1994)","journal-title":"Combinatorica"},{"issue":"7","key":"9625_CR13","first-page":"23","volume":"3","author":"V.G. Vizing","year":"1964","unstructured":"Vizing, V.G.: On an estimate of the chromatic class of a p-graph. Diskretn. Anal. 3(7), 23\u201330 (1964)","journal-title":"Diskretn. Anal."}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-012-9625-7.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00453-012-9625-7\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-012-9625-7","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,29]],"date-time":"2019-05-29T09:45:09Z","timestamp":1559123109000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00453-012-9625-7"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2012,2,24]]},"references-count":13,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2013,5]]}},"alternative-id":["9625"],"URL":"https:\/\/doi.org\/10.1007\/s00453-012-9625-7","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[2012,2,24]]}}}