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
Optimum distance flag codes from spreads via perfect matchings in graphs
Min-Cost Flow in Unit-Capacity Planar Graphs
A $(2 + \epsilon ) k$-vertex kernel for the dual coloring problem
Approximating Largest Convex Hulls for Imprecise Points
The exchange-stable marriage problem
Path factors and parallel knock-out schemes of almost claw-free graphs
Distributed backup placement in networks
A polynomial-time algorithm to determine (almost) Hamiltonicity of dense regular graphs
Computing fair and bottleneck matchings in geometric graphs
Deterministic and probabilistic algorithms for maximum bipartite matching via fast matrix multiplication
Representing triangulated graphs in stars
INNER RECTANGULAR DRAWINGS OF PLANE GRAPHS
Non-cancellative Boolean circuits: A generalization of monotone boolean circuits
An approximation algorithm for the load-balanced semi-matching problem in weighted bipartite graphs
Structural identifiability in low-rank matrix factorization
Flow shop scheduling problem with conflict graphs
Edge coloring of bipartite graphs with constraints
A new fast heuristic for labeling points
On gallery watchmen in grids
Multiconsistency and robustness with global constraints
On the parametric complexity of schedules to minimize tardy tasks.
A linear-time algorithm to find a pair of arc-disjoint spanning in-arborescence and out-arborescence in a directed acyclic graph
Fully dynamic maximal matching in $O(\log n)$ update time (corrected version)
On size reduction techniques for multitape automata
Incremental assignment problem
Two-factors in orientated graphs with forbidden transitions
Solving Kirkman's schoolgirl problem in a few seconds
It is tough to be a plumber
Restrictions and preassignments in preemptive open shop scheduling
Alternating paths along axis-parallel segments
Better approximability results for min-max tree/cycle/path cover problems
Stabilizing maximum matching in bipartite networks
Best of two local models: centralized local and distributed local algorithms
A polynomial algorithm for maximum weighted vertex packings on graphs without long odd cycles
A $5k$-vertex kernel for $P_2$-packing
The asymmetric median tree. --- A new model for building consensus trees
On the $k$-orientability of random graphs
List edge multicoloring in graphs with few cycles
Probabilistic and exact frequent subtree mining in graphs beyond forests
Classes of perfect graphs
Lower bounds for Boolean circuits of bounded negation width
Maximum packing for $k$-connected partial $k$-trees in polynomial time
Efficient simulation of circuits by EREW PRAMs
Structural Identifiability in Low-Rank Matrix Factorization
Embedding partial Steiner triple systems is NP-complete
Computing Euclidean bottleneck matchings in higher dimensions
Iterative Compression and Exact Algorithms
Uniform sampling of $k$-hypertournaments
Variations on instant insanity
Maximizing the number of unused colors in the vertex coloring problem

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)