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

1973/12/01 by John E. Hopcroft, Richard M. Karp · 63 citations
Computer Science · Biochemistry, Genetics and Molecular Biology · Engineering · #Advanced Graph Theory Research #DNA and Biological Computing #graph theory and CDMA systems

paper · doi:10.1137/0202019

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 .Keywordsalgorithmalgorithmic analysisbipartite graphscomputational complexitygraphsmatching

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\n Weight Bipartite Matching
• Phase Transition in Matched Formulas and a Heuristic for Biclique\n 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\n for Worst-Case Time Bounds
• Practical and theoretical improvements for bipartite matching using the\n 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

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