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

1973/12/01 by John E. Hopcroft, Richard M. Karp · 2,849 citations
Biochemistry, Genetics and Molecular Biology · Computer Science · Engineering · Mathematics · #Advanced Graph Theory Research #Algorithm #Bipartite graph #Combinatorics #Computer science #DNA and Biological Computing #Discrete mathematics #Graph #Matching (statistics) #Mathematics #graph theory and CDMA systems

paper · doi:10.1137/0202019

published in SIAM Journal on Computing 2(4), 225-231 (Society for Industrial and Applied Mathematics)

openalex publication_date 1973/12/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/04

Abstract

The present paper shows how to construct a maximum matching in a bipartite graph with n vertices and m edges in a number of computation steps proportional to (m + n)√ n . Keywords algorithm algorithmic analysis bipartite graphs computational complexity graphs matching

Citations

• Paths, Trees, and Flowers

Cited by

• Genome Rearrangements and Sorting by Reversals
• On the Complexity of General Graph Factor Problems
• Deterministic Distributed Edge-Coloring via Hypergraph Maximal Matching
• Asymptotic Improvements on the Exact Matching Distance for 2-parameter Persistence
• Two polynomial algorithms for special maximum matching constructing in trees
• The alldifferent Constraint: A Survey
• DMVP: Foremost Waypoint Coverage of Time-Varying Graphs
• Space-Efficient Interior Point Method, with applications to Linear Programming and Maximum Weight Bipartite Matching
• Online Bipartite Matching with Amortized O(log² n) Replacements
• Polynomial self-stabilizing algorithm and proof for a 2/3-approximation of a maximum matching
• Notes on Hazard-Free Circuits
• Tight Thresholds for Cuckoo Hashing via XORSAT
• Constant Factor Time Optimal Multi-Robot Routing on High-Dimensional Grids in Mostly Sub-Quadratic Time
• Fully Dynamic Matching in Bipartite Graphs
• The iSLIP scheduling algorithm for input-queued switches
• On a Generalization of the Marriage Problem
• Data-driven Policy on Feasibility Determination for the Train Shunting Problem
• Optimum matchings in weighted bipartite graphs
• Bipartite Matching in Nearly-linear Time on Moderately Dense Graphs
• Popular conjectures imply strong lower bounds for dynamic problems
• Geometry Helps to Compare Persistence Diagrams
• On the Complexity of Connectivity in Cognitive Radio Networks Through Spectrum Assignment
• Distribution-free consistent independence tests via center-outward ranks and signs
• Network Alignment by Discrete Ollivier-Ricci Flow
• Optimal Partial Tiling of Manhattan Polyominoes
• Two Disjoint Alternating Paths in Bipartite Graphs: Conformal Crosses
• Faster Matchings via Learned Duals
• Covering Directed Graphs by In-trees
• The Design and Algorithms of a Verification Condition Generator
• Place Bisimilarity is Decidable, Indeed!
• Polynomial-Time Algorithms for Structurally Observable Graphs by Controlling Minimal Vertices
• Notes on Randomized Algorithms
• Vertex Covers Revisited: Indirect Certificates and FPT Algorithms
• Distributed Maximum Matching in Bounded Degree Graphs
• The Complexity of Determining Existence a Hamiltonian Cycle is O(n³)
• GPU accelerated maximum cardinality matching algorithms for bipartite graphs
• Faster Matroid Intersection
• Local Algorithms for Bounded Degree Sparsifiers in Sparse Graphs
• Experimental Evaluation of Modified Decomposition Algorithm for Maximum Weight Bipartite Matching
• Phase Transition in Matched Formulas and a Heuristic for Biclique Satisfiability
• Algorithms and Bounds for Drawing Directed Graphs
• Finding All Allowed Edges in a Bipartite Graph
• A Generalized Matching Reconfiguration Problem
• Multiple D2D Multicasts in Underlay Cellular Networks
• Fully Dynamic Almost-Maximal Matching: Breaking the Polynomial Barrier for Worst-Case Time Bounds
• Practical and theoretical improvements for bipartite matching using the pseudoflow algorithm
• Using Minimum Path Cover to Boost Dynamic Programming on DAGs: Co-Linear Chaining Extended
• Perfect Matchings in Õ(n^1.5) Time in Regular Bipartite Graphs
• Economic Efficiency Requires Interaction
• What is known about Vertex Cover Kernelization?
• Generic Cospark of a Matrix Can Be Computed in Polynomial Time
• Approximate Nearest Neighbors in the Space of Persistence Diagrams
• Data Reduction for Maximum Matching on Real-World Graphs: Theory and Experiments
• The directed Hausdorff distance between imprecise point sets
• An Outage Exponent Region based Coded f-Matching Framework for Channel Allocation in Multi-carrier Multi-access Channels
• Scaling algorithms for approximate and exact maximum weight matching
• An Improved Approximation for Maximum k-Dependent Set on Bipartite\n Graphs
• Minimum Input Selection for Structural Controllability
• Persistence Diagrams and the Heat Equation Homotopy
• Triangle-Free 2-Matchings Revisited
• Efficient algorithms for interval graphs and circular‐arc graphs
• Solving Simultaneous Target Assignment and Path Planning Efficiently with Time-Independent Execution
• A quest for a fair schedule: The Young Physicists' Tournament
• A Geometric Approach to Matrix Ordering
• Unified bijections for planar hypermaps with general cycle-length constraints
• Algorithms for Unipolar and Generalized Split Graphs
• A Decomposition Theorem for Maximum Weight Bipartite Matchings
• Local Computation Algorithms for Graphs of Non-Constant Degrees
• A 9/7-Approximation Algorithm for Graphic TSP in Cubic Bipartite Graphs
• Games on Random Boards
• On the limitations of deterministic de-randomizations for online bipartite matching and max-sat
• On A Generalization of "Eight Blocks to Madness"
• Adventures in Abstraction: Reachability in Hierarchical Drawings
• Minor Sparsifiers and the Distributed Laplacian Paradigm
• Automatic Embedding of Stories Into Collections of Independent Media
• Flows in Almost Linear Time via Adaptive Preconditioning
• The Price of Matching Selfish Vertices
• Generalized Friedland-Tverberg inequality: applications and extensions
• Speeding Up Graph Algorithms via Switching Classes
• Domino tilings and related models: space of configurations of domains with holes
• A linear-time parameterized algorithm for computing the width of a DAG
• On the Convergent Properties of Word Embedding Methods
• The Complexity of HCP in Digraps with Degree Bound Two
• Sublinear Algorithms for (Δ+ 1) Vertex Coloring
• An Optimal Vector Clock Algorithm for Multithreaded Systems
• Linear Programming in the Semi-streaming Model with Application to the Maximum Matching Problem
• A linear time algorithm for L(2,1)-labeling of trees
• Optimal Design of Multiple Description Lattice Vector Quantizers
• Robustness for Non-Parametric Classification: A Generic Attack and Defense
• Stable Marriage with Covering Constraints: A Complete Computational\n Trichotomy
• Greedy Algorithms for Fair Division of Mixed Manna
• Fully dynamic maximal matching in O(log n) update time
• Minor intron–containing genes as an ancient backbone for viral infection?
• Efficient random graph matching via degree profiles
• Maximum Matchings via Glauber Dynamics
• Algorithms and Experiments Comparing Two Hierarchical Drawing Frameworks
• Convergent Learning: Do different neural networks learn the same representations?
• On the Complexity of Several Haplotyping Problems
• On Coloring Unit Disk Graphs
• A New Community Definition For MultiLayer Networks And A Novel Approach For Its Efficient Computation
• Achieving 100% throughput in an input-queued switch
• On the Grundy Number of a Graph
• Group-Theoretic Partial Matrix Multiplication
• Computing the Gromov-Hausdorff Distance for Metric Trees
• Approximation Algorithms for Variable-Sized and Generalized Bin Covering
• Simultaneously Achieving Ex-ante and Ex-post Fairness
• Viral Population Estimation Using Pyrosequencing
• Network Controllability Is Determined by the Density of Low In-Degree and Out-Degree Nodes
• Dinitz’ Algorithm: The Original Version and Even’s Version
• Computing a maximum cardinality matching in a bipartite graph in time O(n1.5)
• The general maximum matching algorithm of micali and vazirani
• Finding Perfect Matchings in Bipartite Hypergraphs
• An O(v|v| c |E|) algoithm for finding maximum matching in general graphs
• Faster scaling algorithms for general graph matching problems
• The Weighted Matching Approach to Maximum Cardinality Matching
• The complexity of completing partial Latin squares
• The complexity of computing the permanent
• Measurable equidecompositions for group actions with an expansion property
• Load adjustment in adaptive real-time systems
• The monotone circuit complexity of boolean functions
• Concerning the achromatic number of graphs
• Bit-vector algorithms for binary constraint satisfaction and subgraph isomorphism
• Depth-first search is inherently sequential
• On the Complexity of Timetable and Multicommodity Flow Problems
• Algorithms for dense graphs and networks on the random access computer
• Network flow and 2-satisfiability
• Greed is good: Approximating independent sets in sparse and bounded-degree graphs
• A REVISION OF MINTY'S ALGORITHM FOR FINDING A MAXIMUM WEIGHT STABLE SET OF A CLAW-FREE GRAPH
• Structural Controllability of Complex Networks Based on Preferential Matching
• Kernelization: Theory of Parameterized Preprocessing
• On Edge Coloring Bipartite Graphs
• Classes of perfect graphs
• Using euler partitions to edge color bipartite multigraphs
• Forests, frames, and games: Algorithms for matroid sums and applications
• Edge-Coloring Bipartite Multigraphs in O ( E log D ) Time
• A FIRST LOOK AT GALAXY FLYBY INTERACTIONS. I. CHARACTERIZING THE FREQUENCY OF FLYBYS IN A COSMOLOGICAL CONTEXT
• Recognition Algorithms for Orders of Small Width and Graphs of Small Dilworth Number
• Structural controllability: an undirected graph approach
• A framework for cost-scaling algorithms for submodular flow problems
• On Path Cover Problems in Digraphs and Applications to Program Testing
• Polynomial algorithms for graph isomorphism and chromatic index on partial k-trees
• The matching problem for bipartite graphs with polynomially bounded permanents is in NC
• A general automatic method for optimal construction of matrix product operators using bipartite graph theory
• Network Flow and Testing Graph Connectivity
• Sparse Highly Connected Spanning Subgraphs in Dense Directed Graphs
• Chromatic index of dense quasirandom graphs
• Simple Deterministic Algorithms for Fully Dynamic Maximal Matching
• Best of Two Local Models: Local Centralized and Local Distributed\n Algorithms
• Node-balancing by edge-increments
• Claw‐Free Graphs, Skeletal Graphs, and a Stronger Conjecture on ω, Δ, and χ
• Maximum skew-symmetric flows and matchings
• Bipartite permutation graphs
• Bipartite graph [wikipedia]
• Hopcroft–Karp algorithm [wikipedia]

Related

• A Faster Combinatorial Algorithm for Maximum Bipartite Matching
• Heuristic to reduce the complexity of complete bipartite graphs to accelerate the search for maximum weighted matchings with small error
• A Decomposition Theorem for Maximum Weight Bipartite Matchings
• A Weighted Approach to the Maximum Cardinality Bipartite Matching Problem with Applications in Geometric Settings
• Approximating Maximum Matching Requires Almost Quadratic Time