{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,3,17]],"date-time":"2024-03-17T12:15:56Z","timestamp":1710677756574},"reference-count":20,"publisher":"Wiley","issue":"2","license":[{"start":{"date-parts":[[2014,12,23]],"date-time":"2014-12-23T00:00:00Z","timestamp":1419292800000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/doi.wiley.com\/10.1002\/tdm_license_1.1"},{"start":{"date-parts":[[2014,12,23]],"date-time":"2014-12-23T00:00:00Z","timestamp":1419292800000},"content-version":"vor","delay-in-days":0,"URL":"http:\/\/onlinelibrary.wiley.com\/termsAndConditions#vor"}],"funder":[{"name":"ISF","award":["903\/2013"]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Random Struct. Alg."],"published-print":{"date-parts":[[2016,3]]},"DOI":"10.1002\/rsa.20578","type":"journal-article","created":{"date-parts":[[2014,12,23]],"date-time":"2014-12-23T23:45:32Z","timestamp":1419378332000},"page":"384-395","source":"Crossref","is-referenced-by-count":6,"title":["Expected time complexity of the auction algorithm and the push relabel algorithm for maximum bipartite matching on random graphs"],"prefix":"10.1002","volume":"48","author":[{"given":"Oshri","family":"Naparstek","sequence":"first","affiliation":[{"name":"School of Engineering; Bar-Ilan University; 52900 Ramat-Gan Israel"}]},{"given":"Amir","family":"Leshem","sequence":"additional","affiliation":[{"name":"School of Engineering; Bar-Ilan University; 52900 Ramat-Gan Israel"}]}],"member":"311","published-online":{"date-parts":[[2014,12,23]]},"reference":[{"key":"10.1002\/rsa.20578-BIB0001|rsa20578-cit-0001","volume-title":"An algorithm for the organization of information","author":"AdelsonVelskii","year":"1963"},{"key":"10.1002\/rsa.20578-BIB0002|rsa20578-cit-0002","doi-asserted-by":"crossref","first-page":"3","DOI":"10.1007\/s00224-005-1254-y","article-title":"Matching algorithms are fast in sparse random graphs","volume":"39","author":"Bast","year":"2006","journal-title":"Theory Comput Syst"},{"key":"10.1002\/rsa.20578-BIB0003|rsa20578-cit-0003","doi-asserted-by":"crossref","first-page":"842","DOI":"10.1073\/pnas.43.9.842","article-title":"Two theorems in graph theory","volume":"43","author":"Berge","year":"1957","journal-title":"Proc Nat Acad Sci USA"},{"key":"10.1002\/rsa.20578-BIB0004|rsa20578-cit-0004","volume-title":"An auction algorithm for shortest paths","author":"Bertsekas","year":"1990"},{"key":"10.1002\/rsa.20578-BIB0005|rsa20578-cit-0005","volume-title":"A distributed algorithm for the assignment problem","author":"Bertsekas","year":"1979"},{"key":"10.1002\/rsa.20578-BIB0006|rsa20578-cit-0006","doi-asserted-by":"crossref","first-page":"277","DOI":"10.1007\/BF00249638","article-title":"A forward\/reverse auction algorithm for asymmetric assignment problems","volume":"1","author":"Bertsekas","year":"1992","journal-title":"Comput Optim Appl"},{"key":"10.1002\/rsa.20578-BIB0007|rsa20578-cit-0007","doi-asserted-by":"crossref","first-page":"24","DOI":"10.1145\/1734213.1734218","article-title":"Finding a maximum matching in a sparse random graph in o (n) expected time","volume":"57","author":"Chebolu","year":"2010","journal-title":"J ACM"},{"key":"10.1002\/rsa.20578-BIB0008|rsa20578-cit-0008","doi-asserted-by":"crossref","first-page":"8","DOI":"10.1145\/297096.297140","article-title":"Augment or push: a computational study of bipartite matching and unit-capacity flow algorithms","volume":"3","author":"Cherkassky","year":"1998","journal-title":"J Exp Algor"},{"key":"10.1002\/rsa.20578-BIB0009|rsa20578-cit-0009","first-page":"1277","article-title":"Algorithm for solution of a problem of maximum flow in networks with power estimation","volume":"11","author":"Dinic","year":"1970","journal-title":"Soviet Math. Dokl"},{"key":"10.1002\/rsa.20578-BIB0010|rsa20578-cit-0010","doi-asserted-by":"crossref","first-page":"359","DOI":"10.1007\/BF01894879","article-title":"On the existence of a factor of degree one of a connected random graph","volume":"17","author":"Erd\u0151s","year":"1966","journal-title":"Acta Math Hungarica"},{"key":"10.1002\/rsa.20578-BIB0011|rsa20578-cit-0011","doi-asserted-by":"crossref","first-page":"123","DOI":"10.1145\/103418.103424","volume-title":"Proceedings of the twenty-third annual ACM symposium on Theory of computing","author":"Feder","year":"1991"},{"key":"10.1002\/rsa.20578-BIB0012|rsa20578-cit-0012","first-page":"39","volume-title":"Proceedings of the 42nd ACM symposium on Theory of computing","author":"Goel","year":"2010"},{"key":"10.1002\/rsa.20578-BIB0013|rsa20578-cit-0013","doi-asserted-by":"crossref","first-page":"153","DOI":"10.1007\/BF01585996","article-title":"An efficient cost scaling algorithm for the assignment problem","volume":"71","author":"Goldberg","year":"1995","journal-title":"Mathematical Programming"},{"key":"10.1002\/rsa.20578-BIB0014|rsa20578-cit-0014","doi-asserted-by":"crossref","first-page":"921","DOI":"10.1145\/48014.61051","article-title":"A new approach to the maximum-flow problem","author":"Goldberg","year":"1988","journal-title":"J ACM"},{"key":"10.1002\/rsa.20578-BIB0015|rsa20578-cit-0015","doi-asserted-by":"crossref","first-page":"225","DOI":"10.1137\/0202019","article-title":"An n^5\/2 algorithm for maximum matchings in bipartite graphs","volume":"2","author":"Hopcroft","year":"1973","journal-title":"SIAM J Comput"},{"key":"10.1002\/rsa.20578-BIB0016|rsa20578-cit-0016","first-page":"1266","article-title":"Push-relabel based algorithms for the maximum transversal problem","author":"Kaya","year":"2012","journal-title":"Comput Oper Res"},{"key":"10.1002\/rsa.20578-BIB0017|rsa20578-cit-0017","doi-asserted-by":"crossref","first-page":"253","DOI":"10.1109\/FOCS.2013.35","volume-title":"2013 IEEE 54th Annual Symposium on","author":"Madry","year":"2013"},{"key":"10.1002\/rsa.20578-BIB0018|rsa20578-cit-0018","doi-asserted-by":"crossref","first-page":"1329","DOI":"10.1145\/195613.195663","article-title":"Average-case analysis of algorithms for matchings and related problems","volume":"41","author":"Motwani","year":"1994","journal-title":"J ACM"},{"key":"10.1002\/rsa.20578-BIB0019|rsa20578-cit-0019","first-page":"211","article-title":"New experimental results for bipartite matching","volume":"93","author":"Setubal","year":"1993","journal-title":"Proc Netflow"},{"key":"10.1002\/rsa.20578-BIB0020|rsa20578-cit-0020","volume-title":"Sequential and parallel experimental results with bipartite matching algorithms","author":"Setubal","year":"1996"}],"container-title":["Random Structures & Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/api.wiley.com\/onlinelibrary\/tdm\/v1\/articles\/10.1002%2Frsa.20578","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/api.wiley.com\/onlinelibrary\/tdm\/v1\/articles\/10.1002%2Frsa.20578","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/onlinelibrary.wiley.com\/wol1\/doi\/10.1002\/rsa.20578\/fullpdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,7,31]],"date-time":"2023-07-31T03:16:56Z","timestamp":1690773416000},"score":1,"resource":{"primary":{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/10.1002\/rsa.20578"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2014,12,23]]},"references-count":20,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2016,3]]}},"URL":"https:\/\/doi.org\/10.1002\/rsa.20578","archive":["Portico"],"relation":{},"ISSN":["1042-9832"],"issn-type":[{"value":"1042-9832","type":"print"}],"subject":[],"published":{"date-parts":[[2014,12,23]]}}}