Hopcroft–Karp algorithm: Difference between revisions

Revision as of 20:50, 18 January 2020

Revision as of 03:25, 10 March 2020

Line 133:

*{{citation|last=Dinitz|first=Yefim|editor1-last=Goldreich|editor1-first=Oded|editor1-link=Oded Goldreich|editor2-last=Rosenberg|editor2-first=Arnold L.|editor2-link=Arnold L. Rosenberg|editor3-last=Selman|editor3-first=Alan L.|contribution=Dinitz' Algorithm: The Original Version and Even's Version|doi=10.1007/11685654_10|___location=Berlin and Heidelberg|pages=218–240|publisher=Springer|series=Lecture Notes in Computer Science|title=Theoretical Computer Science: Essays in Memory of Shimon Even|volume=3895|year=2006}}.

*{{citation | doi = 10.4153/CJM-1965-045-4 | last = Edmonds | first = Jack | author-link = Jack Edmonds | journal = Canadian Journal of Mathematics | pages = 449–467 | title = Paths, Trees and Flowers | volume = 17 | year = 1965 | mr = 0177907}}.

*{{citation|last=Gabow|first=Harold N.|doi=10.3233/FI-2017-1555|issue=1-41–4|journal=Fundamenta Informaticae|mr=3690573|pages=109–130|title=The weighted matching approach to maximum cardinality matching|volume=154|year=2017|arxiv=1703.03998}}

*{{citation|first1=Harold N.|last1=Gabow|first2=Robert E.|last2=Tarjan|author2-link=Robert Tarjan|title=Faster scaling algorithms for general graph matching problems|journal=Journal of the ACM|volume=38|issue=4|year=1991|pages=815–853|doi=10.1145/115234.115366}}.

*{{citation|first1=John E.|last1=Hopcroft|author1-link=John Hopcroft|first2=Richard M.|last2=Karp|author2-link=Richard Karp|title=An ''n''^5/2 algorithm for maximum matchings in bipartite graphs|journal=SIAM Journal on Computing|volume=2|issue=4|pages=225–231|year=1973|doi=10.1137/0202019}}. Previously announced at the 12th Annual Symposium on Switching and Automata Theory, 1971.

*{{citation|first=A. V.|last=Karzanov|authorlink=Alexander V. Karzanov|title=An exact estimate of an algorithm for fnding a maximum flow, applied to the problem on representatives|journal=Problems in Cybernetics|volume=5|pages=66–70|year=1973}}. Previously announced at the Seminar on Combinatorial Mathematics (Moscow, 1971).

*{{citation | last1 = Micali | first1 = S. | author1-link = Silvio Micali | last2 = Vazirani | first2 = V. V. | author2-link = Vijay Vazirani | contribution = An <math>\scriptstyle O(\sqrt{|V|}\cdot|E|)</math> algorithm for finding maximum matching in general graphs | doi = 10.1109/SFCS.1980.12 | pages = 17–27 | title = [[Symposium on Foundations of Computer Science|Proc. 21st IEEE Symp. Foundations of Computer Science]] | year = 1980| title-link = Symposium on Foundations of Computer Science }}.

*{{citation | last1 = Peterson | first1 = Paul A. | last2 = Loui | first2 = Michael C. | title= The general maximum matching algorithm of Micali and Vazirani | doi = 10.1007/BF01762129 | pages = 511–533 | journal= [[Algorithmica]] | year = 1988 | volume=3|issue=1-41–4| citeseerx = 10.1.1.228.9625 }}.

*{{citation|first=Rajeev|last=Motwani|authorlink=Rajeev Motwani|title=Average-case analysis of algorithms for matchings and related problems|year=1994|journal=Journal of the ACM|volume=41|issue=6|pages=1329–1356|doi=10.1145/195613.195663}}.

*{{citation|last=Setubal|first=João C.|contribution=New experimental results for bipartite matching|title=Proc. Netflow93|publisher=Dept. of Informatics, Univ. of Pisa|pages=211–216|year=1993}}. As cited by {{harvtxt|Setubal|1996}}.

*{{citation|last=Setubal|first=João C.|title=Sequential and parallel experimental results with bipartite matching algorithms|publisher=Tech. Rep. IC-96-09, Inst. of Computing, Univ. of Campinas|year=1996|url=http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.48.3539}}.

*{{citation|last=Vazirani|first=Vijay|title=An Improved Definition of Blossoms and a Simpler Proof of the MV Matching Algorithm|publisher= CoRR abs/1210.4594|year=2012|arxiv=1210.4594|bibcode=2012arXiv1210.4594V}}.