{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,10,7]],"date-time":"2026-10-07T21:03:59Z","timestamp":1791407039155,"version":"4.3.3"},"reference-count":20,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"3","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Comput."],"published-print":{"date-parts":[[2013,1]]},"abstract":"<jats:p>In this paper we consider the well-studied problem of finding a perfect matching in a $d$-regular bipartite graph on $2n$ nodes with $m=nd$ edges. The best known algorithm for general bipartite graphs (due to Hopcroft and Karp) takes time $O(m\\sqrt{n})$. In regular bipartite graphs, however, a matching is known to be computable in $O(m)$ time (due to Cole, Ost, and Schirra). In a recent line of work by Goel, Kapralov, and Khanna the $O(m)$ time bound was improved first to $\\tilde O\\left(\\min\\{m, n^{2.5}\/d\\}\\right)$ and then to $\\tilde O\\left(\\min\\{m, n^2\/d\\}\\right)$. In this paper, we give a randomized algorithm that finds a perfect matching in a $d$-regular graph and runs in $O(n\\log n)$ time (both in expectation and with high probability). The algorithm performs an appropriately truncated alternating random walk to successively find augmenting paths. Our algorithm may be viewed as using adaptive uniform sampling, and is thus able to bypass the limitations of (nonadaptive) uniform sampling established in earlier work. Our techniques also give an algorithm that successively finds a matching in the support of a doubly stochastic matrix in expected time $O(n\\log^2 n)$, with $O(m)$ preprocessing time; this gives a simple $O(m+mn\\log^2 n)$ time algorithm for finding the Birkhoff--von Neumann decomposition of a doubly stochastic matrix. We show that randomization is crucial for obtaining $o(nd)$ time algorithms by establishing an $\\Omega(nd)$ lower bound for deterministic algorithms. We also show that there does not exist a randomized algorithm that finds a matching in a regular bipartite multigraph and takes $o(n\\log n)$ time with high probability.<\/jats:p>","DOI":"10.1137\/100812513","type":"journal-article","created":{"date-parts":[[2013,6,25]],"date-time":"2013-06-25T15:07:54Z","timestamp":1372172874000},"page":"1392-1404","source":"Crossref","is-referenced-by-count":21,"title":["Perfect Matchings in $O(n\\log n)$ Time in Regular Bipartite Graphs"],"prefix":"10.1137","volume":"42","author":[{"given":"Ashish","family":"Goel","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Michael","family":"Kapralov","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Sanjeev","family":"Khanna","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2013,6,25]]},"reference":[{"key":"atypb1","doi-asserted-by":"crossref","unstructured":"G. Aggarwal, R. Motwani, D. Shah, and A. Zhu,\n                      Switch scheduling via randomized edge coloring\n                      , in Proceedings of the 44th Annual IEEE Symposium on Foundations of Computer Science, 2003, pp. 502-512.","DOI":"10.1109\/SFCS.2003.1238223"},{"key":"atypb2","first-page":"147","volume":"5","author":"Birkhoff G.","year":"1946","journal-title":"Univ. Nac. Tucum\u00e1n Rev. Ser. A"},{"key":"atypb3","doi-asserted-by":"crossref","unstructured":"B. Bollobas,\n                      Modern Graph Theory\n                      , Springer, New York, 1998.","DOI":"10.1007\/978-1-4612-0619-4"},{"key":"atypb4","doi-asserted-by":"publisher","DOI":"10.1016\/S0140-3664(01)00427-3"},{"key":"atypb5","doi-asserted-by":"publisher","DOI":"10.1137\/0211043"},{"key":"atypb6","doi-asserted-by":"publisher","DOI":"10.1007\/s004930170002"},{"key":"atypb7","first-page":"345","volume":"5","author":"Gabow H. N.","year":"1976","journal-title":"Internat. J. Parallel Programming"},{"key":"atypb8","doi-asserted-by":"publisher","DOI":"10.1137\/0211009"},{"key":"atypb9","doi-asserted-by":"crossref","unstructured":"A. Goel, M. Kapralov, and S. Khanna,\n                      Perfect matchings in $\\tilde{O}(n^{1.5})$ time in regular bipartite graphs\n                      , preprint, http:\/\/arxiv.org\/abs\/0902.1617v2, 2009.","DOI":"10.1145\/1721837.1721843"},{"key":"atypb10","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611973068.2"},{"key":"atypb11","doi-asserted-by":"crossref","unstructured":"T. Hagerup, K. Mehlhorn, and J. I. Munro,\n                      Maintaining discrete probability distributions optimally\n                      , in Proceedings of the 20th International Colloquium on Automata, Languages and Programming (ICALP), 1993, pp. 253-264.","DOI":"10.1007\/3-540-56939-1_77"},{"key":"atypb12","doi-asserted-by":"publisher","DOI":"10.1137\/0202019"},{"key":"atypb13","doi-asserted-by":"publisher","DOI":"10.1006\/jagm.1999.1058"},{"key":"atypb14","doi-asserted-by":"publisher","DOI":"10.1007\/BF01456961"},{"key":"atypb15","doi-asserted-by":"crossref","unstructured":"R. Motwani and P. Raghavan,\n                      Randomized Algorithms\n                      , Cambridge University Press, Cambridge, UK, 1995.","DOI":"10.1017\/CBO9780511814075"},{"key":"atypb16","doi-asserted-by":"publisher","DOI":"10.1137\/S0895480199351136"},{"key":"atypb17","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539796299266"},{"key":"atypb18","unstructured":"H. M. Taylor and S. Karlin,\n                      An Introduction to Stochastic Modeling\n                      , Academic Press, San Diego, CA, 1998."},{"key":"atypb19","first-page":"5","author":"J","year":"1953","journal-title":"NJ"},{"key":"atypb20","doi-asserted-by":"publisher","DOI":"10.1016\/0012-365X(80)90172-7"}],"container-title":["SIAM Journal on Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/100812513","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T18:31:31Z","timestamp":1787337091000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/100812513"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2013,1]]},"references-count":20,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2013,1]]}},"alternative-id":["10.1137\/100812513"],"URL":"https:\/\/doi.org\/10.1137\/100812513","relation":{},"ISSN":["0097-5397","1095-7111"],"issn-type":[{"value":"0097-5397","type":"print"},{"value":"1095-7111","type":"electronic"}],"subject":[],"published":{"date-parts":[[2013,1]]}}}