Perfect matchings via uniform sampling in regular bipartite graphs

MaRDI QIDQ4633805zbMATH OpenFDO

Authors Ashish Goel, Michael Kapralov, Sanjeev Khanna

Publication date 6 May 2019

Full work available at URL https://dl.acm.org/citation.cfm?id=1496772

Mathematics Subject Classification ID

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

Recommendations

• Perfect matchings via uniform sampling in regular bipartite graphs
• Perfect matchings in O(n n) time in regular bipartite graphs
• Perfect matchings in O(n n) time in regular bipartite graphs
• Perfect matchings in \(\tilde{O}(n^{1.5})\) time in regular bipartite graphs
• Exact sampling from perfect matchings of dense regular bipartite graphs

Cited in

(11)

• A simple matching algorithm for regular bipartite graphs.
• Perfect matchings in \(\tilde{O}(n^{1.5})\) time in regular bipartite graphs
• Exact sampling from perfect matchings of dense regular bipartite graphs
• Perfect matchings in O(n n) time in regular bipartite graphs
• Perfect matchings in O(n n) time in regular bipartite graphs
• Perfect matchings via uniform sampling in regular bipartite graphs
• Best Odds for Finding a Perfect Matching in a Bipartite Graph
• Fractional Matching Via Balls-and-Bins
• When Algorithms for Maximal Independent Set and Maximal Matching Run in Sublinear Time
• Matching, edge-colouring, and dimers.
• Perfect matchings in random subgraphs of regular bipartite graphs

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

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