{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2022,4,3]],"date-time":"2022-04-03T21:13:17Z","timestamp":1649020397343},"reference-count":17,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2018,11,28]],"date-time":"2018-11-28T00:00:00Z","timestamp":1543363200000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Combinatorica"],"published-print":{"date-parts":[[2019,4]]},"DOI":"10.1007\/s00493-015-2653-6","type":"journal-article","created":{"date-parts":[[2018,11,28]],"date-time":"2018-11-28T06:53:40Z","timestamp":1543388020000},"page":"323-354","update-policy":"http:\/\/dx.doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Perfect Matchings in \u00d5 (n1.5) Time in Regular Bipartite Graphs"],"prefix":"10.1007","volume":"39","author":[{"given":"Ashish","family":"Goel","sequence":"first","affiliation":[]},{"given":"Michael","family":"Kapralov","sequence":"additional","affiliation":[]},{"given":"Sanjeev","family":"Khanna","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2018,11,28]]},"reference":[{"key":"2653_CR1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.2003.1238223","volume-title":"Switch scheduling via randomized edge coloring","author":"G. Aggarwal","year":"2003","unstructured":"G. Aggarwal, R. Motwani, D. Shah, and A. Zhu: Switch scheduling via randomized edge coloring, FOCS, 2003."},{"key":"2653_CR2","volume-title":"Approximating s-t minimum cuts in ~O (n2) time, Proceedings of the 28th annual ACM^symposium on Theory of computing","author":"A. A. Bencz\u00far","year":"1996","unstructured":"A. A. Bencz\u00far, and D. R. Karger: Approximating s-t minimum cuts in ~O (n2) time, Proceedings of the 28th annual ACM symposium on Theory of computing, 1996."},{"key":"2653_CR3","first-page":"147","volume":"5","author":"G. Birkhoff","year":"1946","unstructured":"G. Birkhoff: Tres observaciones sobre el algebra lineal, Univ. Nac. Tucum\u00e1n Rev. Ser. A\n                           5 (1946), 147\u2013151.","journal-title":"Univ. Nac. Tucum\u00e1n Rev. Ser. A"},{"key":"2653_CR4","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4612-0619-4","volume-title":"Modern graph theory","author":"B. Bollob\u00e1s","year":"1998","unstructured":"B. Bollob\u00e1s: Modern graph theory, Springer, 1998."},{"key":"2653_CR5","doi-asserted-by":"publisher","first-page":"540","DOI":"10.1137\/0211043","volume":"11","author":"R. Cole","year":"1982","unstructured":"R. Cole and J. E. Hopcroft: On edge coloring bipartite graphs. SIAM J. Comput. 11 (1982), 540\u2013546.","journal-title":"SIAM^J.^Comput"},{"key":"2653_CR6","doi-asserted-by":"publisher","first-page":"5","DOI":"10.1007\/s004930170002","volume":"21","author":"R. Cole","year":"2001","unstructured":"R. Cole, K. Ost, and S. Schirra: Edge-coloring bipartite multigraphs in O(ElogD) time, Combinatorica\n                           21 (2001), 5\u201312.","journal-title":"Combinatorica"},{"key":"2653_CR7","doi-asserted-by":"publisher","first-page":"117","DOI":"10.1137\/0211009","volume":"11","author":"H. N. Gabow","year":"1982","unstructured":"H. N. Gabow and O. Kariv:Algorithms for edge coloring bipartite graphs and multigraphs, SIAM J. Comput.\n                           11 (1982), 117\u2013129.","journal-title":"SIAM^J.^Comput."},{"key":"2653_CR8","volume-title":"Proceedings of the Nineteenth Annual ACM -SIAM^Sym-posium on Discrete Algorithms","author":"A. Goel","year":"2009","unstructured":"A. Goel, M. Kapralov, and S. Khanna: Perfect matchings via uniform sampling in regular bipartite graphs, Proceedings of the Nineteenth Annual ACM -SIAM Sym-posium on Discrete Algorithms, 2009."},{"key":"2653_CR9","doi-asserted-by":"publisher","first-page":"225","DOI":"10.1137\/0202019","volume":"2","author":"J. E. Hopcroft","year":"1973","unstructured":"J. E. Hopcroft and R. M. Karp: An n 5 2 algorithm for maximum matchings in bipartite graphs, SIAM J. Comput. 2 (1973), 225\u2013231.","journal-title":"SIAM^J.^Comput"},{"key":"2653_CR10","first-page":"383","volume":"24","author":"D. Karger","year":"1999","unstructured":"D. Karger: Random sampling in cut, flow, and network design problems, Mathe-matics of Operations Research (Preliminary version appeared in the Proceedings of the 26th annual ACM symposium on Theory of computing)\n                           24 (1999), 383\u2013413.","journal-title":"Mathe-matics of Operations Research (Preliminary version appeared in the Proceedings of the 26th annual ACM^symposium on Theory of computing)"},{"key":"2653_CR11","volume-title":"Proceedings of the thiry-fourth annual ACM^symposium on Theory of computing","author":"D. Karger","year":"2002","unstructured":"D. Karger and M. Levine: Random sampling in residual graphs, Proceedings of the thiry-fourth annual ACM symposium on Theory of computing, 2002."},{"key":"2653_CR12","first-page":"601","volume":"43","author":"D. R. Karger","year":"1996","unstructured":"D. R. Karger and C. Stein: A new approach to the minimum cut problem, J. ACM\n                           43 (1996), 601\u2013640.","journal-title":"J.^ACM"},{"key":"2653_CR13","doi-asserted-by":"publisher","first-page":"453","DOI":"10.1007\/BF01456961","volume":"77","author":"D. Konig","year":"1916","unstructured":"D. Konig: Uber graphen und ihre anwendung auf determinententheorie und mengenlehre, Math. Annalen\n                           77 (1916), 453\u2013465.","journal-title":"Math. Annalen"},{"key":"2653_CR14","doi-asserted-by":"publisher","first-page":"1329","DOI":"10.1145\/195613.195663","volume":"41","author":"R. Motwani","year":"1994","unstructured":"R. Motwani: Average-case analysis of algorithms for matchings and related problems, Journal of the ACM(JACM)\n                           41 (1994), 1329\u20131356.","journal-title":"Journal of the ACM(JACM)"},{"key":"2653_CR15","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511814075","volume-title":"Randomized Algorithms","author":"R. Motwani","year":"1995","unstructured":"R. Motwani and P. Raghavan: Randomized Algorithms, Cambridge University Press, 1995."},{"key":"2653_CR16","doi-asserted-by":"publisher","first-page":"841","DOI":"10.1137\/S0097539796299266","volume":"28","author":"A. Schrijver","year":"1999","unstructured":"A. Schrijver: Bipartite edge coloring in O time, SIAM J. on Comput. 28 (1999), 841\u2013846.","journal-title":"SIAM^J.^on Comput"},{"key":"2653_CR17","first-page":"5","volume":"2","author":"J. Neumann von","year":"1953","unstructured":"J. von Neumann: A certain zero-sum two-person game equivalent to the optimal assignment problem, Contributions to the optimal assignment problem to the Theory of Games\n                           2 (1953), 5\u201312.","journal-title":"Contributions to the optimal assignment problem to the Theory of Games"}],"container-title":["Combinatorica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00493-015-2653-6.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00493-015-2653-6\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00493-015-2653-6.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,11,28]],"date-time":"2019-11-28T00:16:46Z","timestamp":1574900206000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00493-015-2653-6"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018,11,28]]},"references-count":17,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2019,4]]}},"alternative-id":["2653"],"URL":"https:\/\/doi.org\/10.1007\/s00493-015-2653-6","relation":{},"ISSN":["0209-9683","1439-6912"],"issn-type":[{"value":"0209-9683","type":"print"},{"value":"1439-6912","type":"electronic"}],"subject":[],"published":{"date-parts":[[2018,11,28]]},"assertion":[{"value":"23 July 2009","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"17 March 2014","order":2,"name":"revised","label":"Revised","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"28 November 2018","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}