Hopcroft–Karp algorithm
In computer science, the 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 that no two edges share an endpoint. It runs in time in the worst case, where is set of edges in the graph, is set of vertices of the graph, and it is assumed that . In the case of dense graphs the time bound becomes , and for sparse random graphs it runs in time with high probability.
- Author1Link
- enJohn Hopcroft
- Author2Link
- enRichard Karp
- Authorlink
- enAlexander V. Karzanov
- Class
- enGraph algorithm
- Comment
- enIn computer science, the 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 that no two edges share an endpoint. It runs in time in the worst case, where is set of edges in the graph, is set of vertices of the graph, and it is assumed that . In the case of dense graphs the time bound becomes , and for sparse random graphs it runs in time with high probability.
- Data
- Graph (data structure)
- Depiction
- First
- enAlexander
- enJohn
- enRichard
- Has abstract
- enIn computer science, the 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 that no two edges share an endpoint. It runs in time in the worst case, where is set of edges in the graph, is set of vertices of the graph, and it is assumed that . In the case of dense graphs the time bound becomes , and for sparse random graphs it runs in time with high probability. The algorithm was discovered by John Hopcroft and Richard Karp and independently by Alexander Karzanov. As in previous methods for matching such as the Hungarian algorithm and the work of , the Hopcroft–Karp algorithm repeatedly increases the size of a partial matching by finding augmenting paths. These paths are sequences of edges of the graph, which alternate between edges in the matching and edges out of the partial matching, and where the initial and final edge are not in the partial matching. Finding an augmenting path allows us to increment the size of the partial matching, by simply toggling the edges of the augmenting path (putting in the partial matching those that were not, and vice versa). Simpler algorithms for bipartite matching, such as the Ford–Fulkerson algorithm‚ find one augmenting path per iteration: the Hopcroft-Karp algorithm instead finds a maximal set of shortest augmenting paths, so as to ensure that only iterations are needed instead of iterations. The same performance of can be achieved to find maximum cardinality matchings in arbitrary graphs, with the more complicated algorithm of Micali and Vazirani. The Hopcroft–Karp algorithm can be seen as a special case of Dinic's algorithm for the maximum flow problem.
- Is primary topic of
- Hopcroft–Karp algorithm
- Label
- enHopcroft–Karp algorithm
- Last
- enHopcroft
- enKarp
- enKarzanov
- Link from a Wikipage to an external page
- www.cs.bgu.ac.il/~dinitz/Papers/Dinitz_alg.pdf%7Cdoi=10.1007/11685654_10%7Clocation=Berlin
- Link from a Wikipage to another Wikipage
- Algorithm
- Algorithmica
- Assignment problem
- Augmenting path
- Average case analysis
- Bipartite graph
- Breadth-first search
- Category:Graph algorithms
- Category:Matching (graph theory)
- Computer science
- Dense graph
- Depth-first search
- Dinic's algorithm
- Edmonds–Karp algorithm
- File:HopcroftKarpExample.png
- Ford–Fulkerson algorithm
- Graph (data structure)
- Hungarian algorithm
- Logarithm
- Maximum cardinality matching
- Maximum flow problem
- Pseudocode
- Push-relabel maximum flow algorithm
- Random graph
- Sparse graph
- Symmetric difference
- Weighted graphs
- Worst case
- SameAs
- Algorithme de Hopcroft-Karp
- Algorithmus von Hopcroft und Karp
- Algoritmo de Hopcroft–Karp
- Hopkroft-Karp algoritam
- m.0fftzf
- Q1516988
- WUaC
- Алгоритм Гопкрофта — Карпа
- Алгоритм Хопкрофта — Карпа
- Հապքրոֆթ-Կարպ ալգորիթմ
- الگوریتم هاپکرافت-کارپ
- خوارزمية هوبكروفت-كارب
- ขั้นตอนวิธีฮอปครอฟท์-คาร์พ
- 霍普克洛夫特－卡普算法
- Subject
- Category:Graph algorithms
- Category:Matching (graph theory)
- Thumbnail
- WasDerivedFrom
- Hopcroft–Karp algorithm?oldid=1116634919&ns=0
- WikiPageLength
- 25147
- Wikipage page ID
- 5944391
- Wikipage revision ID
- 1116634919
- WikiPageUsesTemplate
- Template:Citation
- Template:Cite book
- Template:Harvnb
- Template:Harvs
- Template:Harvtxt
- Template:Infobox algorithm
- Template:Refbegin
- Template:Refend
- Template:Reflist
- Template:Sfnp
- Template:Short description
- Year
- 1973
