{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,21]],"date-time":"2026-01-21T09:58:55Z","timestamp":1768989535683,"version":"3.49.0"},"publisher-location":"Berlin, Heidelberg","reference-count":32,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783540127277","type":"print"},{"value":"9783540387145","type":"electronic"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1983]]},"DOI":"10.1007\/3-540-12727-5_4","type":"book-chapter","created":{"date-parts":[[2012,2,25]],"date-time":"2012-02-25T17:55:18Z","timestamp":1330192518000},"page":"90-113","source":"Crossref","is-referenced-by-count":10,"title":["Efficient algorithms for finding maximal matching in graphs"],"prefix":"10.1007","author":[{"given":"Zvi","family":"Galil","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2005,5,29]]},"reference":[{"key":"4_CR1","volume-title":"The Design and Analysis of Computer Algorithms","author":"A. V. Aho","year":"1974","unstructured":"A.V. Aho, J.E. Hopcroft and J.D. Ullman, The Design and Analysis of Computer Algorithms, Addison-Wesley, Reading, Mass., 1974."},{"key":"4_CR2","first-page":"144","volume":"18","author":"D. Angluin","year":"1979","unstructured":"D. Angluin and L.G. Valiant, Fast probabilistic algorithms for Hamiltonian paths and matchings, JCSS 18 (1979), 144\u2013193.","journal-title":"JCSS"},{"key":"4_CR3","doi-asserted-by":"crossref","unstructured":"A. Borodin, J. von zur Gathen and J.E. Hopcroft, Fast parallel and gcd computations, Proc. 23rd IEEE Symp. on FOCS (1982), 64\u201371.","DOI":"10.1109\/SFCS.1982.17"},{"key":"4_CR4","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. on Computing 11 (1982), 540\u2013546.","journal-title":"SIAM J. on Computing"},{"key":"4_CR5","doi-asserted-by":"publisher","first-page":"263","DOI":"10.1007\/BF01386390","volume":"1","author":"E. W. Dijkstra","year":"1959","unstructured":"E.W. Dijkstra, A note on two problems in connexion with graphs, Numer. Math. 1 (1959), 263\u2013271.","journal-title":"Numer. Math."},{"key":"4_CR6","first-page":"1277","volume":"11","author":"E. A. Dinic","year":"1970","unstructured":"E.A. Dinic, Algorithm for solution of a problem of maximal flow in a network with power estimation, Soviet Math. Dokl. 11 (1970), 1277\u20131280.","journal-title":"Soviet Math. Dokl."},{"key":"4_CR7","doi-asserted-by":"crossref","first-page":"449","DOI":"10.4153\/CJM-1965-045-4","volume":"17","author":"J. Edmonds","year":"1965","unstructured":"J. Edmonds, Path, trees and flowers, Canad. J. Math. 17 (1965), 449\u2013467.","journal-title":"Canad. J. Math."},{"key":"4_CR8","first-page":"125","volume":"698","author":"J. Edmonds","year":"1965","unstructured":"J. Edmonds, Maximum matching and a polyhedron with 0,1 vertices, J. Res. NBS, 698 (April\u2013June 1965), 125\u2013130.","journal-title":"J. Res. NBS"},{"key":"4_CR9","doi-asserted-by":"crossref","unstructured":"S. Even and O. Kariv, An O(n2.5) algorithm for maximum matching in graphs, Proc. 16th IEEE Symp. on FOCS (1975), 100\u2013112.","DOI":"10.1109\/SFCS.1975.5"},{"key":"4_CR10","doi-asserted-by":"publisher","first-page":"507","DOI":"10.1137\/0204043","volume":"4","author":"S. Even","year":"1975","unstructured":"S. Even and R.E. Tarjan, Network flow and testing graph connectivity, SIAM J. on Comput. 4 (1975), 507\u2013518.","journal-title":"SIAM J. on Comput."},{"issue":"3","key":"4_CR11","doi-asserted-by":"crossref","first-page":"399","DOI":"10.4153\/CJM-1956-045-5","volume":"8","author":"L. R. Ford","year":"1956","unstructured":"L.R. Ford, and D.R. Fulkerson, Maximal flow through a network, Canadian J. Math. 8, 3 (1956), 399\u2013404.","journal-title":"Canadian J. Math."},{"key":"4_CR12","unstructured":"H.N. Gabow, Implementation of algorithms for maximum matching on nonbipartite graphs, Ph.D. Thesis, Department of Computer Science, Stanford University, 1974."},{"key":"4_CR13","doi-asserted-by":"publisher","first-page":"221","DOI":"10.1145\/321941.321942","volume":"23","author":"H. N. Gabow","year":"1976","unstructured":"H.N. Gabow, An efficient implementation of Edmonds' algorithm for maximum matching on graphs, J. ACM 23 (1976), 221\u2013234.","journal-title":"J. ACM"},{"key":"4_CR14","doi-asserted-by":"publisher","first-page":"345","DOI":"10.1007\/BF00998632","volume":"5","author":"H. N. Gabow","year":"1976","unstructured":"H.N. Gabow, Using Euler partitions to edge color bipartite multigraphs, International J. of Computer and Information Sciences 5 (1976) 345\u2013355.","journal-title":"International J. of Computer and Information Sciences"},{"key":"4_CR15","unstructured":"H.N. Gabow, An efficient reduction technique for degree-constrained subgraph and bidirection network flow problems, to appear in Proc. 14th ACM STOC."},{"key":"4_CR16","doi-asserted-by":"crossref","first-page":"221","DOI":"10.1007\/BF00264254","volume":"14","author":"Z. Galil","year":"1980","unstructured":"Z. Galil, An O(E2\/3V5\/3) algorithm for the maximal flow problem, Acta Information 14 (1980), 221\u2013242.","journal-title":"Acta Information"},{"key":"4_CR17","first-page":"407","volume":"22","author":"O. Gabber","year":"1981","unstructured":"O. Gabber and Z. Galil, Explicit construction of linear-sized super concentrators, JCSS 22 (1981), 407\u2013420.","journal-title":"JCSS"},{"key":"4_CR18","doi-asserted-by":"crossref","unstructured":"Z. Galil, S. Micali and H.N. Gabow, Priority queues with variable priority and an O(EV log V) algorithm for finding a maximal weighted matching in general graphs, Proc. 23rd IEEE Symp. on FOCS (1982), 255\u2013261.","DOI":"10.1109\/SFCS.1982.36"},{"key":"4_CR19","doi-asserted-by":"crossref","unstructured":"H.N. Gabow and R.E. Tarjan, A linear time algorithm for a special case of disjoint set union, manuscript, July 1982 (to ppear in Proc. 14th ACM STOC).","DOI":"10.1145\/800061.808753"},{"key":"4_CR20","doi-asserted-by":"publisher","first-page":"105","DOI":"10.1016\/0304-3975(82)90092-5","volume":"21","author":"L. Goldschlager","year":"1982","unstructured":"L. Goldschlager, R. Shaw, and J. Staples, the maximum flow problem is log space complete for P, TCS 21 (1982), 105\u2013111.","journal-title":"TCS"},{"key":"4_CR21","doi-asserted-by":"publisher","first-page":"206","DOI":"10.1016\/0020-0190(81)90103-4","volume":"12","author":"M. Iri","year":"1981","unstructured":"M. Iri, K. Murota and S. Matsui, Linear time approximation algorithms for finding the minimum weight perfect matching on a plane, Info. Proc. Letters 12 (1981), 206\u2013209.","journal-title":"Info. Proc. Letters"},{"key":"4_CR22","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/321992.321993","volume":"24","author":"D. Johnson","year":"1977","unstructured":"D. Johnson, Efficient algorithms for shortest paths in sparse graphs, J. ACM 24 (1977), 1\u201313.","journal-title":"J. ACM"},{"key":"4_CR23","volume-title":"An O(n2.5) algorithm for maximal matching in general graphs","author":"O. Kariv","year":"1976","unstructured":"O. Kariv, An O(n2.5) algorithm for maximal matching in general graphs, Ph.D. Thesis, Department of Applied Mathematics, The Weizman Inst., Rehovot, Israel, 1976."},{"issue":"2","key":"4_CR24","doi-asserted-by":"crossref","first-page":"143","DOI":"10.1002\/net.3230100205","volume":"10","author":"R. M. Karp","year":"1980","unstructured":"R.M. Karp, An algorithm to solve the assignment problem in expected time O(mn log n), Network 10, 2 (1980), 143\u2013152.","journal-title":"Network"},{"key":"4_CR25","volume-title":"The Art of Computer Programming, Vol 3: Sorting and Searching","author":"D. E. Knuth","year":"1973","unstructured":"D.E. Knuth, The Art of Computer Programming, Vol 3: Sorting and Searching, Addison-Wesley, Reading, Mass., 1973."},{"key":"4_CR26","doi-asserted-by":"crossref","first-page":"91","DOI":"10.1007\/BF02239502","volume":"12","author":"T. Kameda","year":"1974","unstructured":"T. Kameda and I. Munro, A O(|V|\u00b7|E|) algorithm for maximum matching of graphs, Computing 12 (1974), 91\u201398.","journal-title":"Computing"},{"key":"4_CR27","doi-asserted-by":"crossref","unstructured":"R.M. Karp and M. Sipser, Maximal matchings in sparse graphs, Proc. 22nd IEEE Symp. on FOCS (1981), 364\u2013375.","DOI":"10.1109\/SFCS.1981.21"},{"key":"4_CR28","volume-title":"Combinatorial Optimization: Networds and Matroids","author":"E. L. Lawler","year":"1976","unstructured":"E.L. Lawler, Combinatorial Optimization: Networds and Matroids, Holt, Rienhard and Winston, New York, 1976."},{"key":"4_CR29","doi-asserted-by":"crossref","unstructured":"S. Micali and V.V. Vazirani, An O(\u221a|V|\u00b7|E|) algorithm for finding maximum matching in general graphs, Proc. 21st IEEE Symp. on FOCS (1980), 17\u201327.","DOI":"10.1109\/SFCS.1980.12"},{"key":"4_CR30","unstructured":"A.O. Slisenko, Recognition of palindromes by multihead Turing machines, in Problems in the Constructive Trend in Mathematics, VI (Proc. of the Steklov Institute of Mathematics 129), V.P. Orevkov and N.A. Sanin (eds.), Academy of Sciences of the USSR (1973), 30\u2013202; English translation by R.H. Silverman, American Math. Society, Providence, Rhode Island (1976), 25\u2013208."},{"key":"4_CR31","doi-asserted-by":"publisher","first-page":"215","DOI":"10.1145\/321879.321884","volume":"22","author":"R. E. Tarjan","year":"1975","unstructured":"R.E. Tarjan, Efficiency of a good but not linear set union algorithm, J. ACM 22, (1975), 215\u2013225.","journal-title":"J. ACM"},{"key":"4_CR32","doi-asserted-by":"crossref","first-page":"25","DOI":"10.1002\/net.3230070103","volume":"7","author":"R. E. Tarjan","year":"1977","unstructured":"R.E. Tarjan, Finding optimum branchings, Network 7 (1977), 25\u201335.","journal-title":"Network"}],"container-title":["Lecture Notes in Computer Science","CAAP'83"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-12727-5_4.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,11,17]],"date-time":"2020-11-17T20:06:15Z","timestamp":1605643575000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-12727-5_4"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1983]]},"ISBN":["9783540127277","9783540387145"],"references-count":32,"URL":"https:\/\/doi.org\/10.1007\/3-540-12727-5_4","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[1983]]}}}