An n^{5/2} Algorithm for Maximum Matchings in Bipartite Graphs

Cited in

(only showing first 100 items - show all)

Approximating largest convex hulls for imprecise points
The stable marriage problem with master preference lists
Stabilizing maximum matching in bipartite networks
On the k-orientability of random graphs
An approximation algorithm for multidimensional assignment problems minimizing the sum of squared errors
List edge multicoloring in graphs with few cycles
Approximation algorithms for hard variants of the stable marriage and hospitals/residents problems
Optimal movement of mobile sensors for barrier coverage of a planar region
Efficient bounds for the stable set, vertex cover and set packing problems
Detection of structural inconsistency in systems of equations with degrees of freedom and its applications
Depth-first search is inherently sequential
Sensitivity analysis of an agricultural linear programming model
Concerning the achromatic number of graphs
On the complexity of a family of generalized matching problems
Lower bounds on monotone complexity of the logical permanent
Scaling algorithms for network problems
On gallery watchmen in grids
An O(n log n log log n) parallel maximum matching algorithm for bipartite graphs
Bipartite permutation graphs
Recursive structure of S-matrices and an O(m^ 2) algorithm for recognizing sign solvability
The monotone circuit complexity of Boolean functions
On a scheduling problem where a job can be executed only by a limited number of processors
The general maximum matching algorithm of Micali and Vazirani
The discrete time-cost tradeoff problem revisited
Systems of distinct representatives for k families of sets
Degree switching operations in networks and large scale systems assignment problems
Maximum matchings and trees
On generalized matching problems
Deterministic and probabilistic algorithms for maximum bipartite matching via fast matrix multiplication
Algorithms for minimum covering by cliques and maximum clique in claw- free perfect graphs
The complexity of testing whether a graph is a superconcentrator
An algorithm for matrix symmetrization
The complexity of computing metric distances between partitions
Depth-first search and the vertex cover problem
The isomorphism problem for classes of graphs closed under contraction
The translation square map and approximate congruence
Forests, frames, and games: Algorithms for matroid sums and applications
New scaling algorithms for the assignment and minimum mean cycle problems
Branch-and-bound algorithms for the multi-product assembly line balancing problem
Matching theory -- a sampler: From Dénes König to the present
Minimum perfect bipartite matchings and spanning trees under categorization
On the complexity of finding iso- and other morphisms for partial $k$- trees
Finding a maximum matching in a circular-arc graph
A note on degree-constrained star subgraphs of bipartite graphs
Linear algorithms for testing the sign stability of a matrix and for finding Z-maximum matchings in acyclic graphs
A remark on the time complexity of the subtree problem
Representing triangulated graphs in stars
Approximating matchings in parallel
On the use of the complexity index as a measure of complexity in activity networks
Approximating the permanent via importance sampling with application to the dimer covering problem
A linear algorithm for perfect matching in hexagonal systems
Network flow and 2-satisfiability
A theory of alternating paths and blossoms for proving correctness of the $O(\sqrt{V}E)$ general graph maximum matching algorithm
Finding all the perfect matchings in bipartite graphs
A graph theory approach to subcontracting, machine duplication and intercell moves in cellular manufacturing
Periodic assignment and graph colouring
Maximizing the number of unused colors in the vertex coloring problem
Finding maximum matching for bipartite graphs in parallel
Clique covering and clique partition in generalizations of line graphs
Tiling figures of the plane with two bars
Circular convex bipartite graphs: Maximum matching and Hamiltonian circuits
A polynomial-time algorithm for reducing the number of variables in MAX SAT problem
Solution methods and computational investigations for the linear bottleneck assignment problem
Activity nets: A guided tour through some recent developments
Maximum tree-packing in time $O(n^{5/2})$
Triangulating multitolerance graphs
Scalar aggregation in inconsistent databases.
Small maximal matchings in random graphs.
Pushdown-reduce: An algorithm for connectivity augmentation and poset covering problems
On the complexity of graph tree partition problems.
Non-cancellative Boolean circuits: A generalization of monotone boolean circuits
Computing Euclidean bottleneck matchings in higher dimensions
Concurrent operations can be parallelized in scheduling multiprocessor job shop
Matchings in colored bipartite networks
Orthogonal layout with optimal face complexity
Constraint programming and operations research
Optimizing the controllability of arbitrary networks with genetic algorithm
Characterizing the topological and controllability features of U.S. power transmission networks
A (3+)k-vertex kernel for edge-disjoint triangle packing
The stochastic stability of decentralized matching on a graph
Efficient subgraph matching using topological node feature constraints
A fast scaling algorithm for the weighted triangle-free 2-matching problem
Gross substitutability: an algorithmic survey
Polynomial time algorithms for variants of graph matching on partial k-trees
Minimum-cost flows in unit-capacity networks
Flow shop scheduling problem with conflict graphs
Graphs vertex-partitionable into strong cliques
On the parameterized complexity of $(k,s)$-SAT
Network alignment by discrete Ollivier-Ricci flow
Algorithms and bounds for drawing directed graphs
A marriage matching mechanism menagerie
Mathematical models for stable matching problems with ties and incomplete lists
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
Distributed backup placement in networks
Complexity analyses for multi-agent scheduling problems with a global agent and equal length jobs
$b$-coloring of tight graphs
Solving Kirkman's schoolgirl problem in a few seconds
The geometry of partial fitness orders and an efficient method for detecting genetic interactions

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)