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)

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
On the fixed controllable subspace in linear structured 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
Structural solvability of systems of equations —A mathematical formulation for distinguishing accurate and inaccurate numbers in structural analysis of systems—
Graphs vertex-partitionable into strong cliques
Another disjoint compression algorithm for odd cycle transversal
On some algorithmic investigations of star partitions of graphs
Authentication codes and bipartite graphs
Bounded Unpopularity Matchings
Matchings in colored bipartite networks
A self-stabilizing $\frac23$-approximation algorithm for the maximum matching problem
The Simple Reachability Problem in Switch Graphs
On Some Problems in the Design of Plane Skeletal Structures
On complexity of special maximum matchings constructing
Iterative improvement of vertex covers
Local computation algorithms for graphs of non-constant degrees
Iterated local search with Trellis-neighborhood for the partial Latin square extension problem
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

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)