Maximum matchings in general graphs through randomization
From MaRDI portal
Publication:3031945
DOI10.1016/0196-6774(89)90005-9zbMath0689.68092WikidataQ56341082 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
68R10: Graph theory (including graph drawing) in computer science
05C70: Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.)
Related Items
Perfect Matching in General vs. Cubic Graphs: A Note on the Planar and Bipartite Cases, Parallel output-sensitive algorithms for combinatorial and linear algebra problems, Subtree isomorphism is in random NC, Maximum weight bipartite matching in matrix multiplication time, Matching is as easy as matrix inversion, Constructing a perfect matching is in random NC, Matching theory -- a sampler: From Dénes König to the present, Maximum matchings in planar graphs via Gaussian elimination, Processor efficient parallel matching