Perfect matchings via uniform sampling in regular bipartite graphs

DOI10.1145/1721837.1721843zbMath1300.05252arXiv0811.2457OpenAlexW2151348756MaRDI QIDQ2930303

Michael Kapralov, Ashish Goel, Sanjeev Khanna

Publication date: 18 November 2014

Published in: ACM Transactions on Algorithms (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/0811.2457

zbMATH Keywords

perfect matchingregular bipartite graphs

Mathematics Subject Classification ID

Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Coloring of graphs and hypergraphs (05C15) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items (4)

Spectral sparsification in the semi-streaming setting ⋮ Perfect matchings in random subgraphs of regular bipartite graphs ⋮ Maximum matching in regular and almost regular graphs ⋮ On the threshold problem for Latin boxes

This page was built for publication: Perfect matchings via uniform sampling in regular bipartite graphs