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

DOI10.1137/0202019zbMATH Open0266.05114DBLPjournals/siamcomp/HopcroftK73OpenAlexW2157529519WikidataQ55891586 ScholiaQ55891586MaRDI QIDQ5682014FDOQ5682014

Cited In (only showing first 100 items - show all)

Algorithms and bounds for drawing directed graphs
A marriage matching mechanism menagerie
Closing complexity gaps for coloring problems on $H$-free graphs
On the maximum edge-pair embedding bipartite matching
Fixed-parameter tractability of $(n-k)$ list coloring
Constraint programming and operations research
Orthogonal layout with optimal face complexity
A parameterized algorithmics framework for degree sequence completion problems in directed graphs
Parameterized algorithms and kernels for rainbow matching
On extensions of the deterministic online model for bipartite matching and max-sat
A planner-optimal matching mechanism and its incentive compatibility in a restricted domain
Optimizing the controllability of arbitrary networks with genetic algorithm
Characterizing the topological and controllability features of U.S. power transmission networks
On improving matchings in trees, via bounded-length augmentations
Fully dynamic matching in bipartite graphs
Efficient and flexible matching of recursive types
On maximum bipartite matching with separation
Approximate constrained bipartite edge coloring
A $(3+\epsilon)k$-vertex kernel for edge-disjoint triangle packing
Gross substitutability: an algorithmic survey
Complexity analyses for multi-agent scheduling problems with a global agent and equal length jobs
The sparse awakens: streaming algorithms for matching size estimation in sparse graphs
Improved algorithms for even factors and square-free simple $b$-matchings
Geometry helps to compare persistence diagrams
A structure theorem for rooted binary phylogenetic networks and its implications for tree-based networks
Finding a maximum matching in a permutation graph
Complexity results for rainbow matchings
On $(s,t)$-relaxed $L(2,1)$-labeling of graphs
New characterisations of tree-based networks and proximity measures
Lattice complete graphs
Maximum matching width: new characterizations and a fast algorithm for dominating set
The stochastic stability of decentralized matching on a graph
Computing maximum non-crossing matching in convex bipartite graphs
Contraction and deletion blockers for perfect graphs and $H$-free graphs
The geometry of partial fitness orders and an efficient method for detecting genetic interactions
Efficient algorithms for scheduling equal-length jobs with processing set restrictions on uniform parallel batch machines
On the power of simple reductions for the maximum independent set problem
Efficient subgraph matching using topological node feature constraints
A fast scaling algorithm for the weighted triangle-free 2-matching problem
Triangle-free 2-matchings revisited
Special parity of perfect matchings in bipartite graphs
A linear-time algorithm for maximum-cardinality matching on cocomparability graphs
A polynomial-time maximum common subgraph algorithm for outerplanar graphs and its application to chemoinformatics
Claw-free graphs, skeletal graphs, and a stronger conjecture on $\omega$, $\Delta$, and $\chi$
Faster algorithm for finding maximum 1-restricted simple 2-matchings
Title not available (Why is that?)
Using Minimum Path Cover to Boost Dynamic Programming on DAGs: Co-linear Chaining Extended
Recovery of disrupted airline operations using $k$-maximum matching in graphs
On the parameterized complexity of $(k,s)$-SAT
Edge-stable equimatchable graphs
A survey of direct methods for sparse linear systems
Throughput analysis in wireless networks with multiple users and multiple channels
Recursive structure of S-matrices and an $O(m^ 2)$ algorithm for recognizing sign solvability
An efficient distributed algorithm for maximum matching in general graphs
Using euler partitions to edge color bipartite multigraphs
Level scheduling under limited resequencing flexibility
Maximum bipartite flow in networks with adaptive channel width
The extended global cardinality constraint: an empirical survey
Packings by Complete Bipartite Graphs
Bottleneck partial-matching Voronoi diagrams and applications
On the complexity of graph reconstruction
A simple existence criterion for $(g<f)$-factors
Approximate string matching with stuck address bits
The complexity of testing whether a graph is a superconcentrator
An approximation algorithm for multidimensional assignment problems minimizing the sum of squared errors
Parallel algorithms for bipartite matching problems on distributed memory computers
Sensitivity analysis of linear systems—a structural approach
On completing latin squares
Solution methods and computational investigations for the linear bottleneck assignment problem
A polynomial-time algorithm for computing the resilience of arrangements of ray sensors
Distributed scheduling for disconnected cooperation
Cliques in hyperbolic random graphs
Enhancing multi-document summarization using concepts
Counting houses of Pareto optimal matchings in the house allocation problem
A combinatorial study of the rigidity of planar structures
Computing simple circuits from a set of line segments
Stable matchings with covering constraints: a complete computational trichotomy
Domino tilings and related models: Space of configurations of domains with holes
Structural control of single-input rank one bilinear systems
Solving subgraph isomorphism problems with constraint programming
The complexity of computing metric distances between partitions
On the complexity of graph tree partition problems.
A remark on the time complexity of the subtree problem
A perfect matching algorithm for sparse bipartite graphs
Algorithms for unipolar and generalized split graphs
Solving linear programs from sign patterns
Branch-and-reduce exponential/FPT algorithms in practice: a case study of vertex cover
AllDifferent-based filtering for subgraph isomorphism
Making sparse matrices sparser: Computational results
Generalised arc consistency for the AllDifferent constraint: an empirical survey
On strongly connected digraphs with bounded cycle length
GEOMETRIC ALGORITHMS FOR STATIC LEAF SEQUENCING PROBLEMS IN RADIATION THERAPY
Graph-theoretical approach to qualitative solvability of linear systems
Quantum algorithms for matching problems
Covering directed graphs by in-trees
Noisy colored point set matching
Approximating edge dominating set in dense graphs
Jump number of dags having Dilworth number 2
An approximation of the minimum vertex cover in a graph
Using relations to develop a Haskell program for computing maximum bipartite matchings

This page was built for publication: An $n^{5/2} $ Algorithm for Maximum Matchings in Bipartite Graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5682014)