A n^5/2 Algorithm for Maximum Matchings in Bipartite Graphs

By John E. Hopcroft, Richard M. Karp. 1971

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

Citations in the corpus

Convergent Learning: Do different neural networks learn the same representations? (2015, methodology): “This more common approach is known as bipartite matching.7 A matching that maximizes the sum of the chosen correlation values may be found efficiently via the Hopcroft-Karp algorithm (Hopcroft & Karp, 1973) after turning the between-net correlation matrix into a weighted bipartite graph.”
Recursive Partitioning for Personalization using Observational Data (2016, background): “3 P � This problem can be reduced to bi-partite matching, which can be solved efﬁciently (Hopcroft & Karp, 1973).”
Graphs-at-a-time: query language and access methods for graph databases (2008, background): “The overall time complexity is O(l · ∑k i=1 |Φ(ui)| · (d1d2 + M(d1, d2))) where l is the refinement level, d1 and d2 are maximum degrees of P and G respectively, and M() is the time complexity of maximum bipartite matching (O(n) for Hopcroft and Karp’s algorithm [16]).”
Modeling inter-camera space-time and appearance relationships for tracking across non-overlapping views (2008, methodology): “The maximum matching of a bipartite graph can be found by an O(n) algorithm by Hopcroft and Karp [11], where n is the total number of vertices in graph G, i.”
Experimental and Efficient Algorithms (2003, methodology): “Other definitions can be found in [8, 11].”
Popular Conjectures Imply Strong Lower Bounds for Dynamic Problems (2014, methodology): “In a breakthrough paper earlier this year, Madry [65] devised the first improvement over the Hopcroft-Karp algorithm for sparse bipartite graphs, with a runtime of Õ(m10/7).”
Control Principles of Complex Networks (2015, methodology): “A maximum matching of a bipartite graph can be found efficiently using the Hopcroft-Karp algorithm, which runs in O( √ V E) time (Hopcroft and Karp, 1973).”
Distribution-Free Consistent Independence Tests via Center-Outward Ranks and Signs (2019, methodology): “It is essentially the combination of the Hungarian method (Kuhn 1955, 1956; Munkres 1957) and the algorithm of Hopcroft and Karp (1973).”
Maximum Flow and Minimum-Cost Flow in Almost-Linear Time (2022, background): “A long line of work led to a running time of O ( m min { m 1 / 2 , n 2 / 3 } log U ) [29, 31, 23, 27] for max-ﬂow, and O ( mn log U ) [26] for min-cost ﬂow.”
Similarity-Based Ontology Alignment in OWL-Lite (2004, background): “There has been important background work that can be used for ontology alignment: in discrete mathematics for matching graphs and trees [7, 11], in databases for reconciling and merging schemas [12], in machine learning for clustering compound objects described in a restricted first order logic [1].”
Closure-Tree: An Index Structure for Graph Queries (2006, methodology): “If it is unweighted, then the maximum matching is computed using Hopcroft and Karp’s algorithm [16].”