Computing a maximum cardinality matching in a bipartite graph in time \(O(n^{1,5}\sqrt{m/\log \,n})\)
From MaRDI portal
Publication:751274
DOI10.1016/0020-0190(91)90195-NzbMath0714.68036OpenAlexW1541277988WikidataQ56626048 ScholiaQ56626048MaRDI QIDQ751274
Publication date: 1991
Published in: Information Processing Letters (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/0020-0190(91)90195-n
Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)
Related Items (41)
Optimum matchings in weighted bipartite graphs ⋮ Persistency in maximum cardinality bipartite matchings ⋮ Distinguishing and classifying from \(n\)-ary properties ⋮ Improved complexity bound for the maximum cardinality bottleneck bipartite matching problem ⋮ Complexity of a disjoint matching problem on bipartite graphs ⋮ Characterization of vertex pancyclic and pancyclic ordinary complete multipartite digraphs ⋮ Linear-Time Approximation for Maximum Weight Matching ⋮ Generalised arc consistency for the AllDifferent constraint: an empirical survey ⋮ Parameterized complexity of \(k\)-anonymity: hardness and tractability ⋮ Solution methods and computational investigations for the linear bottleneck assignment problem ⋮ Hardness and approximation of minimum maximal matchings ⋮ Algorithms for dense graphs and networks on the random access computer ⋮ Solving Matching Problems Efficiently in Bipartite Graphs ⋮ The balanced traveling salesman problem ⋮ Finding all maximally-matchable edges in a bipartite graph ⋮ Stability, vertex stability, and unfrozenness for special graph classes ⋮ Minimum Leaf Out-Branching Problems ⋮ Bottleneck partial-matching Voronoi diagrams and applications ⋮ A Distributed-Memory Algorithm for Computing a Heavy-Weight Perfect Matching on Bipartite Graphs ⋮ Dulmage-Mendelsohn canonical decomposition as a generic pruning technique ⋮ Edge $k$-$q$-Colorability of Graphs ⋮ Perfect matchings and extended polymatroid ⋮ Trapezoid graphs and generalizations, geometry and algorithms ⋮ On complexity of special maximum matchings constructing ⋮ An O(\(n\)) time algorithm for maximum matching on cographs ⋮ A polynomial algorithm to find an independent set of maximum weight in a fork-free graph ⋮ Selected topics on assignment problems ⋮ Trapezoid graphs and generalizations, geometry and algorithms ⋮ Sweep synchronization as a global propagation mechanism ⋮ Parallel algorithms for bipartite matching problems on distributed memory computers ⋮ Perfectly matchable subgraph problem on a bipartite graph ⋮ Algorithms for unipolar and generalized split graphs ⋮ Multiple bottleneck assignment problem ⋮ Minimum leaf out-branching and related problems ⋮ On uniform \(k\)-partition problems ⋮ Weakly Hamiltonian-connected ordinary multipartite tournaments ⋮ Alternating paths in edge-colored complete graphs ⋮ OPTIMAL PARALLEL MATCHING ON BIPARTITE PERMUTATION GRAPHS ⋮ Polynomial-time recognition of minimal unsatisfiable formulas with fixed clause-variable difference. ⋮ A linear time algorithm for the maximum matching problem on cographs ⋮ Perfect Matching in General vs. Cubic Graphs: A Note on the Planar and Bipartite Cases
Cites Work
This page was built for publication: Computing a maximum cardinality matching in a bipartite graph in time \(O(n^{1,5}\sqrt{m/\log \,n})\)
