Maximum matchings in general graphs through randomization
From MaRDI portal
Publication:3031945
DOI10.1016/0196-6774(89)90005-9zbMath0689.68092OpenAlexW2089939118WikidataQ56341082 ScholiaQ56341082MaRDI QIDQ3031945
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
Graph theory (including graph drawing) in computer science (68R10) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)
Related Items
Maximum matchings in planar graphs via Gaussian elimination, Fast Output-Sensitive Matrix Multiplication, Matching is as easy as matrix inversion, Constructing a perfect matching is in random NC, Maximum matchings in geometric intersection graphs, Unnamed Item, A deterministic parallel reduction from weighted matroid intersection search to decision, Finding all maximally-matchable edges in a bipartite graph, Subtree isomorphism is in random NC, Bi-criteria and approximation algorithms for restricted matchings, Processor efficient parallel matching, Diverse Pairs of Matchings, Matching theory -- a sampler: From Dénes König to the present, Structural results on matching estimation with applications to streaming, Parallel output-sensitive algorithms for combinatorial and linear algebra problems, Approximating multistage matching problems, Approximating multistage matching problems, Going beyond dual execution: MPC for functions with efficient verification, Optimizing Sparse Matrix—Matrix Multiplication for the GPU, Maximum weight bipartite matching in matrix multiplication time, Algorithms for Weighted Matching Generalizations I: Bipartite Graphs, b-matching, and Unweighted f-factors, Unnamed Item, Perfect Matching in General vs. Cubic Graphs: A Note on the Planar and Bipartite Cases