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 fast algorithm to construct a representation for transversal matroids
Optimum matchings in weighted bipartite graphs
Eccentricity, center and radius computations on the cover graphs of distributive lattices with applications to stable matchings
The complexity of computing the permanent
Finding all maximally-matchable edges in a bipartite graph
A fixed-parameter algorithm for the vertex cover $P_3$ problem
Fair matchings and related problems
Masking traveling beams: optical solutions for NP-complete problems, trading space for time
Selected topics on assignment problems
Computing a maximum cardinality matching in a bipartite graph in time $O(n^{1,5}\sqrt{m/\log \,n})$
The complexity of completing partial Latin squares
A fixed-parameter-tractable algorithm for set packing
An efficient bounds consistency algorithm for the global cardinality constraint
Looking at the stars
Scheduling jobs with equal processing times subject to machine eligibility constraints
The stable marriage problem with master preference lists
On vertex independence number of uniform hypergraphs
Scaling algorithms for network problems
Perfect matchings in hexagonal systems
Signsolvability revisited
Depth-first search and the vertex cover problem
Exact and approximate computational geometry solutions of an unrestricted point set stereo matching problem
Distinguishing and classifying from $n$-ary properties
Finding all the perfect matchings in bipartite graphs
Periodic assignment and graph colouring
A polynomial algorithm for the extendability problem in bipartite graphs
Detection of structural inconsistency in systems of equations with degrees of freedom and its applications
A polynomial time solvable instance of the feasible minimum cover problem
A $\frac{9}{7}$-approximation algorithm for graphic TSP in cubic bipartite graphs
Efficient algorithms with performance guarantees for some problems of finding several discrete disjoint subgraphs in complete weighted graph
Forests, frames, and games: Algorithms for matroid sums and applications
New scaling algorithms for the assignment and minimum mean cycle problems
Greed is good: Approximating independent sets in sparse and bounded-degree graphs
Parameterized tractability of the maximum-duo preservation string mapping problem
A note on the complexity of the causal ordering problem
Bipartite permutation graphs
On the asymptotic optimality of an algorithm for solving the maximum $m$-PSP in a multidimensional Euclidean space
Efficient random graph matching via degree profiles
A parallel algorithm for finding a maximum clique of a set of circular arcs of a circle
Dulmage-Mendelsohn canonical decomposition as a generic pruning technique
A polynomial algorithm to find an independent set of maximum weight in a fork-free graph
Depth-first search is inherently sequential
Fast domino tileability
Activity nets: A guided tour through some recent developments
Enhancing complex network controllability by minimum link direction reversal
Matching theory -- a sampler: From Dénes König to the present
The translation square map and approximate congruence
Linear-time approximation for maximum weight matching
The monotone circuit complexity of Boolean functions
Implicit computation of maximum bipartite matchings by sublinear functional operations
A scaling algorithm for maximum weight matching in bipartite graphs
A theory of alternating paths and blossoms for proving correctness of the $O(\sqrt{V}E)$ general graph maximum matching algorithm
The general maximum matching algorithm of Micali and Vazirani
A parameterized perspective on packing paths of length two
An exact reformulation algorithm for large nonconvex nLPs involving bilinear terms
$b$-coloring of tight graphs
Algorithms for maximum matching and minimum fill-in on chordal bipartite graphs
Approximating matchings in parallel
An algorithm for fractional assignment problems
On the use of the complexity index as a measure of complexity in activity networks
Computation of approximate polynomial GCDs and an extension
Finding a complete matching with the maximum product on weighted bipartite graphs
Circular convex bipartite graphs: Maximum matching and Hamiltonian circuits
The discrete time-cost tradeoff problem revisited
The isomorphism problem for classes of graphs closed under contraction
Reducing rank-maximal to maximum weight matching
The single-input minimal controllability problem for structured systems
Complexity of learning in concept lattices from positive and negative examples
Tiling figures of the plane with two bars
A simpler linear time $ \frac{2}{3} - \varepsilon$ approximation for maximum weight matching
Oriented star packings
A survey on labeling graphs with a condition at distance two
Minimum-cost flows in unit-capacity networks
Branch-and-bound algorithms for the multi-product assembly line balancing problem
On the complexity of finding iso- and other morphisms for partial $k$- trees
On the Grundy number of a graph
Toughness, hamiltonicity and split graphs
Maximum matching of given weight in complete and complete bipartite graphs
On global warming: Flow-based soft global constraints
Fixed-parameter algorithms for scaffold filling
A fixed-parameter tractable algorithm for matrix domination
Network alignment by discrete Ollivier-Ricci flow
Iterative compression and exact algorithms
Distribution-Free Consistent Independence Tests via Center-Outward Ranks and Signs
On balanced graphs
DECOMPOSITION OF GEOMETRIC CONSTRAINT SYSTEMS: A SURVEY
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

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)