The Hopcroft-Karp algorithm finds a maximum cardinality matching in a bipartite graph by repeatedly finding a maximal set of shortest augmenting paths using a breadth-first search phase followed by a depth-first search phase that augments the matching along each found path, increasing the matching size in rounds until no augmenting path remains. John Hopcroft and Richard Karp published it in 1973, and it runs in O(E times the square root of V) time, an improvement over the O(VE) time of earlier augmenting path methods for bipartite matching. It remains the standard efficient algorithm for bipartite maximum matching problems such as job assignment.
Facts
Time Complexity
Time Complexity (category)Polynomial Time -- O(n^k) 1 Credited ToJohn Hopcroft and Richard Karp (1973) 2 Connections
In Field
Source Wikipedia: Hopcroft-Karp algorithm
Invented By
John Hopcroft co-developed this algorithm for finding maximum cardinality matchings in bipartite graphs with Richard Karp, published in 1973.
Source Wikipedia: John Hopcroft
Richard Karp co-developed this algorithm for finding maximum cardinality matchings in bipartite graphs with John Hopcroft, published in 1973.
Source Wikipedia: Richard M. Karp
Sources
1. Hopcroft-Karp Algorithm (Wikipedia)
Wikipedia infobox: time complexity polynomialQuote, Wikipedia infobox: time complexity polynomial
polynomial
2. Wikipedia: Hopcroft-Karp algorithm
Lead section
The algorithm was discovered by John Hopcroft and Richard Karp (1973) and independently by
In Field: Algorithms and Complexity Theory, Lead sentence
Hopcroft-Karp algorithm (sometimes more accurately called the Hopcroft-Karp-Karzanov algorithm) is an algorithm that takes a bipartite graph as input and produces a maximum-cardinality matching as output, a set of as many edges as possible with the property t
View the SourceReader Challenges (0)
No disputes yet. Spotted an error or a better source? Open the first one.
Sign in to dispute this or suggest a correction.