{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2020,6,11]],"date-time":"2020-06-11T18:06:41Z","timestamp":1591898801850},"reference-count":54,"publisher":"Association for Computing Machinery (ACM)","issue":"1","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["ACM Comput. Surv."],"published-print":{"date-parts":[[1986,3]]},"DOI":"10.1145\/6462.6502","type":"journal-article","created":{"date-parts":[[2002,7,27]],"date-time":"2002-07-27T11:32:04Z","timestamp":1027769524000},"page":"23-38","source":"Crossref","is-referenced-by-count":240,"title":["Efficient algorithms for finding maximum matching in graphs"],"prefix":"10.1145","volume":"18","author":[{"given":"Zvi","family":"Galil","sequence":"first","affiliation":[{"name":"Columbia Univ., New York, NY; and Tel-Aviv Univ., Tel-Aviv, Israel"}]}],"member":"320","reference":[{"key":"e_1_2_1_1_1","unstructured":"AHO A. V. HOPCROFT J. E. AND ULLMAN J. D. 1974. The Design and Analysis of Computer Algorithms. Addison-Wesley Reading Mass. AHO A. V. HOPCROFT J. E. AND ULLMAN J. D. 1974. The Design and Analysis of Computer Algorithms. Addison-Wesley Reading Mass."},{"key":"e_1_2_1_2_1","first-page":"144","article-title":"Fast probabilistic algorithms for Hamiltonian paths and matchings","volume":"18","author":"ANCLUIN D.","year":"1979","journal-title":"J. Comput. Syst. Sci."},{"key":"e_1_2_1_3_1","doi-asserted-by":"crossref","first-page":"517","DOI":"10.1002\/net.3230130406","article-title":"An analysis of alternative strategies for implementing matching algorithms","volume":"13","author":"BALL M. O.","year":"1983","journal-title":"Network"},{"key":"e_1_2_1_4_1","doi-asserted-by":"crossref","first-page":"842","DOI":"10.1073\/pnas.43.9.842","article-title":"Two theorems in graph theory","volume":"43","author":"BEROE C.","year":"1957","journal-title":"Proc. Nat. Acad. Sci."},{"key":"e_1_2_1_5_1","unstructured":"Proceedings o{ the 23rd Annual IEEE Symposlum on Foundations of Computer Science. IEEE New York Proceedings o{ the 23rd Annual IEEE Symposlum on Foundations of Computer Science. IEEE A. BORODIN J. VON ZUR GATHEN J. E. HOPCROFT Fast parallel and gcd computations 1982 64 71"},{"key":"e_1_2_1_6_1","doi-asserted-by":"crossref","first-page":"540","DOI":"10.1137\/0211043","article-title":"On edge coloring bipartite graphs","volume":"11","author":"COLE R.","year":"1982","journal-title":"SIAM J. Comput."},{"key":"e_1_2_1_7_1","doi-asserted-by":"crossref","first-page":"472","DOI":"10.1137\/0211038","article-title":"On the asymptotic complexity of matrix multiplication","volume":"11","author":"COPPERSMITH D.","year":"1982","journal-title":"SIAM J. Comput."},{"key":"e_1_2_1_8_1","author":"DERIGS U.","first-page":"379","year":"1981","article-title":"A shortest augmenting path method for solving minimal perfect matching problems","journal-title":"Networks","DOI":"10.1002\/net.3230110407","doi-asserted-by":"crossref"},{"key":"e_1_2_1_9_1","unstructured":"DERIGS U. 1982. Shortest augmenting paths and sensitivity analysis for optimal matchings. Rep. 82222-OR Institut f\/Jr Okonometrie und Operations Research Univ. Bonn West Germany April. DERIGS U. 1982. Shortest augmenting paths and sensitivity analysis for optimal matchings. Rep. 82222-OR Institut f\/Jr Okonometrie und Operations Research Univ. Bonn West Germany April."},{"key":"e_1_2_1_10_1","doi-asserted-by":"crossref","first-page":"263","DOI":"10.1007\/BF01386390","article-title":"A note on two problems in connexion with graphs","volume":"1","author":"DIJKSTRA E. W.","year":"1959","journal-title":"Numer. Math."},{"key":"e_1_2_1_11_1","first-page":"1277","article-title":"Algorithm for solution of a problem of maximal flow in a network with power estimation","volume":"11","author":"DINIC E. A.","year":"1970","journal-title":"Sov. Math. Dokl."},{"key":"e_1_2_1_12_1","doi-asserted-by":"crossref","first-page":"449","DOI":"10.4153\/CJM-1965-045-4","article-title":"Path, trees and flowers","volume":"17","author":"EDMONDS J.","year":"1965","journal-title":"Can. J. Math."},{"key":"e_1_2_1_13_1","first-page":"125","article-title":"Matching and a polyhedron with 0,1 vertices","volume":"69","author":"EDMONDS J.","year":"1965","journal-title":"J. Res. N. B. S. B"},{"key":"e_1_2_1_14_1","unstructured":"Proceedings of the 16th Annual IEEE Symposium on Foundations of Computer Science. IEEE New York Proceedings of the 16th Annual IEEE Symposium on Foundations of Computer Science. IEEE S. EVEN V O KAR An O(n2'5) algorithm for maximum matching in graphs 1975 100 112"},{"key":"e_1_2_1_15_1","doi-asserted-by":"crossref","first-page":"507","DOI":"10.1137\/0204043","article-title":"Network flow and testing graph connectivity","volume":"4","author":"EVEN S.","year":"1975","journal-title":"SIAM J. Comput"},{"key":"e_1_2_1_16_1","doi-asserted-by":"crossref","first-page":"399","DOI":"10.4153\/CJM-1956-045-5","article-title":"Maximal flow through a network","volume":"8","author":"FORD L. R.","year":"1956","journal-title":"Can. J. Math"},{"key":"e_1_2_1_17_1","unstructured":"Proceedings of the 25th Annual IEEE Symposium on Foundations of Computer Science. IEEE New York Proceedings of the 25th Annual IEEE Symposium on Foundations of Computer Science. IEEE M. L. FREOMAN R. E. TARJAN Fibonacci heaps and their uses (in improved network optimization algorithms) 1984 338 346"},{"key":"e_1_2_1_18_1","doi-asserted-by":"crossref","first-page":"407","DOI":"10.1016\/0022-0000(81)90040-4","article-title":"Explicit construction of linear-sized superconcentrators","volume":"22","author":"GABBER O.","year":"1981","journal-title":"J. Comput. Syst. Sci."},{"key":"e_1_2_1_19_1","unstructured":"GABOW H. N. 1974. Implementation of algorithms for maximum matching on nonbipartite graphs. Ph.D. dissertation Dept. of Computer Science Stanford Univ. Stanford Calif. GABOW H. N. 1974. Implementation of algorithms for maximum matching on nonbipartite graphs. Ph.D. dissertation Dept. of Computer Science Stanford Univ. Stanford Calif."},{"key":"e_1_2_1_20_1","DOI":"10.1145\/321941.321942","doi-asserted-by":"publisher"},{"key":"e_1_2_1_21_1","first-page":"344","article-title":"Using Euler partitions to edge color bipartite multigraphs. Int. J. Comput. In{","volume":"5","author":"GABOW H. N.","year":"1976","journal-title":"Sci."},{"key":"e_1_2_1_22_1","unstructured":"Proceedings of the 15th Annual A CM Symposium on Theory of Computing Boston Apr. 25-27). ACM New York Proceedings of the 15th Annual A CM Symposium on Theory of Computing H. N. GABOW An efficient reduction technique for degree-constrained subgraphs and bidirected network flow problems 1983 448 456 10.1145\/800061.808776 10.1145\/800061.808776 10.1145\/800061.808776"},{"key":"e_1_2_1_23_1","unstructured":"Proceedings of the 24th Annual IEEE Symposium on Foundations o{ Computer Science. IEEE New York Proceedings of the 24th Annual IEEE Symposium on Foundations o{ Computer Science. IEEE H. N. GABOW Scaling algorithms for network problems 1983 248 257"},{"key":"e_1_2_1_24_1","unstructured":"Proceedings o{ the 26th Annual IEEE Symposium on Foundations of Computer Science. IEEE New York Proceedings o{ the 26th Annual IEEE Symposium on Foundations of Computer Science. IEEE H. N. GABOW A scaling algorithm for weighted matching on general graphs 1985 90 100"},{"key":"e_1_2_1_25_1","unstructured":"Proceedings of the 15th Annual ACM Symposium on Theory of Computing Boston Apr. 25-27). ACM New York Proceedings of the 15th Annual ACM Symposium on Theory of Computing H. N. GABOW R. E. TARJAN A linear time algorithm for a special case of disjoint set union 1983 246 251 10.1145\/800061.808753 10.1145\/800061.808753 10.1145\/800061.808753"},{"key":"e_1_2_1_26_1","unstructured":"Proceedings o{ the 25th Annual IEEE Symposium on Foundations o{ Computer Science. IEEE New York Proceedings o{ the 25th Annual IEEE Symposium on Foundations o{ Computer Science. IEEE H. N. GABOW Z. GALIL T. H. SPENCER Efficient implementation of graph algorithms using contraction 1984 347 357"},{"key":"e_1_2_1_27_1","doi-asserted-by":"crossref","first-page":"221","DOI":"10.1007\/BF00264254","article-title":"An O(E2\/SVS\/a) algorithm for the maximal flow problem","volume":"14","author":"GALIL Z.","year":"1980","journal-title":"Acta Inf."},{"key":"e_1_2_1_28_1","unstructured":"Proceedings of the 26th Annual IEEE Symposium on Foundations of Computer Science. IEEE New York Proceedings of the 26th Annual IEEE Symposium on Foundations of Computer Science. IEEE Z. GALIL V. PAN Improved processor bounds for algebraic and combinatorial problems in RNC 1985 490 495"},{"key":"e_1_2_1_29_1","DOI":"10.1137\/0215009","doi-asserted-by":"publisher"},{"key":"e_1_2_1_30_1","doi-asserted-by":"crossref","first-page":"187","DOI":"10.1007\/BF01582245","article-title":"Efficient dual simplex algorithms for the assignment problem","volume":"33","author":"GOLDFARB D.","year":"1985","journal-title":"Math. Program."},{"key":"e_1_2_1_31_1","doi-asserted-by":"crossref","first-page":"105","DOI":"10.1016\/0304-3975(82)90092-5","article-title":"The maximum flow problem is log space complete for P","volume":"21","author":"GOLDSCHLAGER L.","year":"1982","journal-title":"Theor. Comput. Sci."},{"key":"e_1_2_1_32_1","doi-asserted-by":"crossref","first-page":"225","DOI":"10.1137\/0202019","article-title":"N5\/2 algorithm for maximum matchings in bipartite graphs","volume":"2","author":"HOPCROFT J. E.","year":"1973","journal-title":"SIAM J. Comput."},{"key":"e_1_2_1_33_1","doi-asserted-by":"crossref","first-page":"206","DOI":"10.1016\/0020-0190(81)90103-4","article-title":"Linear time approximation algorithms for finding the minimum weight perfect matching on a plan","volume":"12","author":"IRI M.","year":"1981","journal-title":"Inf. Process. Lett."},{"key":"e_1_2_1_34_1","DOI":"10.1145\/321992.321993","doi-asserted-by":"publisher"},{"key":"e_1_2_1_35_1","unstructured":"KARIV O. 1976. An O(nz~) algorithm for maximal matching in general graphs. Ph.D. dissertation Dept. of Applied Mathematics The Weizmann Institute Rehovot Israel. KARIV O. 1976. An O(nz~) algorithm for maximal matching in general graphs. Ph.D. dissertation Dept. of Applied Mathematics The Weizmann Institute Rehovot Israel."},{"key":"e_1_2_1_36_1","doi-asserted-by":"crossref","first-page":"143","DOI":"10.1002\/net.3230100205","article-title":"An algorithm to solve the assignment problem in expected time O(mn log n)","volume":"10","author":"KARP R. M.","year":"1980","journal-title":"Network"},{"key":"e_1_2_1_37_1","unstructured":"Proceedings of the 22nd IEEE Symposium on Foundations of Computer Science. iEEE New York Proceedings of the 22nd IEEE Symposium on Foundations of Computer Science. iEEE R. M. KARP M. SIPSER Maximal matchings in sparse graphs 1981 364 375"},{"key":"e_1_2_1_38_1","unstructured":"Proceedings of the 17th Annual ACM Symposium on Theory of Computing (Providence R.I. May 6-8). ACM New York Proceedings of the 17th Annual ACM Symposium on Theory of Computing (Providence R.I. May 6-8). ACM R. M. KARP E. UPFAL A. WIGOERSON Constructing a perfect matching is in random NC 1985 22 32 10.1145\/22145.22148 10.1145\/22145.22148 10.1145\/22145.22148"},{"key":"e_1_2_1_39_1","unstructured":"KNUTH D. E. 1973. The Art o{ Computer Programming. Vol. 3 Sorting and Searching. Addison- Wesley Reading Mass. KNUTH D. E. 1973. The Art o{ Computer Programming. Vol. 3 Sorting and Searching. Addison- Wesley Reading Mass."},{"key":"e_1_2_1_40_1","first-page":"253","article-title":"The Hungarian method for the assignment problem","volume":"2","author":"KUHN H. W.","year":"1955","journal-title":"Naval Res. Logist. Quart"},{"key":"e_1_2_1_41_1","author":"LAWLER E. L.","year":"1976","volume-title":"Combinatorial Optimization: Networks and Matroids. Holt, Rinehart and Winston"},{"key":"e_1_2_1_42_1","unstructured":"Proceedings of the 21st Annual IEEE Symposium on Foundations of Computer Science. IEEE New York Proceedings of the 21st Annual IEEE Symposium on Foundations of Computer Science. IEEE S. MICALI Ni V VAZ V. An of value algorithm for finding maximal matching in general graphs 1980 17 27"},{"key":"e_1_2_1_43_1","unstructured":"MULMULEY K. VAZIRANi U. V. AND VAZIRANI V. V. 1985. Matching is as easy as matrix inversion. Manuscript MSRI Berkeley Berkeley Calif. MULMULEY K. VAZIRANi U. V. AND VAZIRANI V. V. 1985. Matching is as easy as matrix inversion. Manuscript MSRI Berkeley Berkeley Calif."},{"key":"e_1_2_1_44_1","doi-asserted-by":"crossref","first-page":"315","DOI":"10.1090\/S0002-9939-1959-0106853-5","article-title":"An algorithm for a minimum cover of a graph","volume":"0","author":"NORMAN R. Z.","year":"1959","journal-title":"Proc. Am. Math. Soc."},{"key":"e_1_2_1_45_1","unstructured":"PAPADIMITRIOU C. H. AND STEIGLITZ $. 1982. Combinatorial Optimization Algorithms and Complexity. Prentice-Hall Englewood Cliffs N.J. PAPADIMITRIOU C. H. AND STEIGLITZ $. 1982. Combinatorial Optimization Algorithms and Complexity. Prentice-Hall Englewood Cliffs N.J."},{"key":"e_1_2_1_46_1","doi-asserted-by":"crossref","first-page":"163","DOI":"10.1016\/0196-6774(84)90024-5","article-title":"Heuristic matching for graphs satisfying the triangle inequality","volume":"5","author":"PLAISTED D. A.","year":"1984","journal-title":"J. Algorithms"},{"key":"e_1_2_1_47_1","unstructured":"RABIN M. O. AND VAZIRAN! V. V. 1984. Maximum matchings in general graphs through randomization. Rep. TR-15-84 Center for Research in Computing Technology Harvard Univ. Cambridge Mass. Oct. RABIN M. O. AND VAZIRAN! V. V. 1984. Maximum matchings in general graphs through randomization. Rep. TR-15-84 Center for Research in Computing Technology Harvard Univ. Cambridge Mass. Oct."},{"key":"e_1_2_1_48_1","unstructured":"Proceedings of the Steklov Institute o{ Mathematics Orevkov and N. A. Sanin Eds. Academy of Sciences of the U.S.S.R. Proceedings of the Steklov Institute o{ Mathematics 129 A. O. SLISENKO Recognition of palindromes by multihead Turing machines. In Problems in the Constructive Trend in Mathematics. VI 1973 30 202"},{"key":"e_1_2_1_49_1","doi-asserted-by":"crossref","first-page":"11","DOI":"10.1016\/0020-0190(82)90077-1","article-title":"NP- completeness of some generalizations of the maximum matching problem","volume":"15","author":"STOCKMEYER L. J.","year":"1982","journal-title":"Inf. Process. Lett."},{"key":"e_1_2_1_50_1","DOI":"10.1145\/321879.321884","doi-asserted-by":"publisher"},{"key":"e_1_2_1_51_1","doi-asserted-by":"crossref","first-page":"25","DOI":"10.1002\/net.3230070103","article-title":"Finding optimum branchings","volume":"7","author":"TARJAN R. E.","year":"1977","journal-title":"Network"},{"key":"e_1_2_1_52_1","unstructured":"TARJAN R. E. 1983. Data structures and network algorithms. SIAM publications. TARJAN R. E. 1983. Data structures and network algorithms. SIAM publications.","DOI":"10.1137\/1.9781611970265","doi-asserted-by":"crossref"},{"key":"e_1_2_1_53_1","doi-asserted-by":"crossref","first-page":"41","DOI":"10.1002\/net.3230110105","article-title":"Sensitivity analysis of optimal matchings","volume":"11","author":"WEBER G.","year":"1981","journal-title":"Networks"},{"key":"e_1_2_1_54_1","doi-asserted-by":"crossref","first-page":"91","DOI":"10.1007\/BF02239502","article-title":"O(}V{ ~ }El) algorithm for maximum matching of graphs","volume":"12","author":"KAMEOA T.","year":"1974","journal-title":"Computing"}],"container-title":["ACM Computing Surveys (CSUR)"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/dl.acm.org\/ft_gateway.cfm?id=6502&ftid=20025&dwn=1","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,2,16]],"date-time":"2020-02-16T19:07:23Z","timestamp":1581880043000},"score":1.0,"subtitle":[],"short-title":[],"issued":{"date-parts":[[1986,3]]},"references-count":54,"journal-issue":{"published-print":{"date-parts":[[1986,3]]},"issue":"1"},"alternative-id":["10.1145\/6462.6502"],"URL":"http:\/\/dx.doi.org\/10.1145\/6462.6502","relation":{"cites":[]},"ISSN":["0360-0300","1557-7341"],"issn-type":[{"value":"0360-0300","type":"print"},{"value":"1557-7341","type":"electronic"}]}}