Maximum matchings in general graphs through randomization

DOI10.1016/0196-6774(89)90005-9MaRDI QIDQ3031945zbMATH OpenOpenAlexDBLPWikidataFDO

Authors Michael O. Rabin, Vijay V. Vazirani

Publication date 1989

Published in Journal of Algorithms (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0196-6774(89)90005-9

zbMATH Keywords

maximum matching problemrandomized algorithmTutte matrix

Mathematics Subject Classification ID

Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph theory (including graph drawing) in computer science (68R10)

Recommendations

• Matching is as easy as matrix inversion
• A fast and simple randomized parallel algorithm for maximal matching
• A Las Vegas RNC algorithm for maximum matching
• STACS 2004
• Matching algorithms are fast in sparse random graphs

Cited in

(42)

• Maximum weight bipartite matching in matrix multiplication time
• Maximum matchings in a class of random graphs
• Matching is as easy as matrix inversion
• A Las Vegas RNC algorithm for maximum matching
• Constructing a perfect matching is in random NC
• The general maximum matching algorithm of Micali and Vazirani
• Matching theory -- a sampler: From Dénes König to the present
• Small maximal matchings in random graphs.
• An algebraic matching algorithm
• Structural results on matching estimation with applications to streaming
• Finding a maximum matching in a permutation graph
• Going beyond dual execution: MPC for functions with efficient verification
• Maximum matchings in planar graphs via Gaussian elimination
• Matching algorithms are fast in sparse random graphs
• Bi-criteria and approximation algorithms for restricted matchings
• Processor efficient parallel matching
• Optimizing sparse matrix-matrix multiplication for the GPU
• A Fast Perfect-Matching Algorithm in Random Graphs
• Fast Output-Sensitive Matrix Multiplication
• Finding all maximally-matchable edges in a bipartite graph
• scientific article; zbMATH DE number 1962832 (Why is no real title available?)
• Perfect Matching in General vs. Cubic Graphs: A Note on the Planar and Bipartite Cases
• scientific article; zbMATH DE number 6866348 (Why is no real title available?)
• The time complexity of maximum matching by simulated annealing
• Maximal matchings in graphs with large neighborhoods of independent vertices
• scientific article; zbMATH DE number 7359421 (Why is no real title available?)
• Algorithms – ESA 2004
• Algorithms for weighted matching generalizations. I: Bipartite graphs, b-matching, and unweighted f-factors
• Approximating multistage matching problems
• Approximating multistage matching problems
• Parallel output-sensitive algorithms for combinatorial and linear algebra problems
• Maximum matchings in geometric intersection graphs
• Diverse Pairs of Matchings
• A deterministic parallel reduction from weighted matroid intersection search to decision
• Proportionally Fair Matching with Multiple Groups
• Diverse pairs of matchings
• A simple randomized parallel algorithm for maximal f-matchings
• Maximum flow and minimum-cost flow in almost-linear time
• Faster algorithms on linear delta-matroids
• A near-optimal polynomial distance lemma over Boolean slices
• Edge-coloured graphs with only monochromatic perfect matchings and their connection to quantum physics
• Subtree isomorphism is in random NC

This page was built for publication: Maximum matchings in general graphs through randomization

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3031945)