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)

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
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
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
A Polynomial-Time Algorithm to Determine (Almost) Hamiltonicity of Dense Regular Graphs
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
Fully Dynamic Maximal Matching in $O(\log n)$ Update Time (Corrected Version)
Maximizing the number of unused colors in the vertex coloring problem
Deadlock-freedom in resource contentions
Title not available (Why is that?)
Mathematical models for stable matching problems with ties and incomplete lists
Attributed relational graph matching based on the nested assignment structure
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
Title not available (Why is that?)
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

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)