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
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
On testing monomials in multivariate polynomials
The generalized popular condensation problem
Bit-Parallel Tree Pattern Matching Algorithms for Unordered Labeled Trees
Linear time approximation algorithms for~degree~constrained subgraph problems
Concerning the achromatic number of graphs
Distance three labelings of trees
Complexities of efficient solutions of rectilinear polygon cover problems
A polynomial case of the parsimony haplotyping problem
Approximating the permanent via importance sampling with application to the dimer covering problem
The directed Hausdorff distance between imprecise point sets
Matchability and $k$-maximal matchings
Constrained target controllability of complex networks
Tiling with Squares and Packing Dominos in Polynomial Time
A new framework for hierarchical drawings
Application of an algorithm for calculating the maximum density subgraph to the schedule optimization problem
A polynomial-time algorithm for reducing the number of variables in MAX SAT problem
Jump number of two-directional orthogonal ray graphs
Bipartite matching in the semi-streaming model
Crown reductions for the minimum weighted vertex cover problem
Lattice path matroids: structural properties
Approximating the minimum clique cover and other hard problems in subtree filament graphs
A General Testability Theory
Efficient bounds for the stable set, vertex cover and set packing problems
Optimizing restriction site placement for synthetic genomes
Characterization of generic properties of linear structured systems for efficient computations.
Sweep synchronization as a global propagation mechanism
On protein structure alignment under distance constraint
On generalized matching problems
A theory of rectangular dual graphs
Polynomial time algorithms for variants of graph matching on partial $k$-trees
Ridesharing for emergency evacuation
An O$(n^{1.75})$ algorithm for $L(2,1)$-labeling of trees
A linear time algorithm for $L(2,1)$-labeling of trees
Communication and energy efficient routing protocols for single-hop radio networks
Polynomial-time recognition of minimal unsatisfiable formulas with fixed clause-variable difference.
Algorithms for the transportation problem in geometric settings

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)