A determinant-based algorithm for counting perfect matchings in a general graph

MaRDI QIDQ5501332zbMATH OpenFDO

Authors Steve Chien

Publication date 3 August 2015

Mathematics Subject Classification ID

Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25)

Recommendations

• On counting perfect matchings in general graphs
• Exact sampling from perfect matchings of dense regular bipartite graphs
• scientific article; zbMATH DE number 1962833
• Scaling matrices and counting the perfect matchings in graphs
• Randomized sequential importance sampling for estimating the number of perfect matchings in bipartite graphs

Cited in

(12)

• On counting 3-D matchings of size \(k\)
• A simple a. s. correct algorithm for deciding if a graph has a perfect matching
• Counting the number of perfect matchings, and generalized decision trees
• Scaling matrices and counting the perfect matchings in graphs
• On counting perfect matchings in general graphs
• Hafnians, perfect matchings and Gaussian matrices
• A polynomial-time approximation algorithm for the number of k-matchings in bipartite graphs
• scientific article; zbMATH DE number 15862 (Why is no real title available?)
• scientific article; zbMATH DE number 1962833 (Why is no real title available?)
• The number of matchings in random graphs
• Counting perfect matchings as fast as Ryser
• Exact algorithms for exact satisfiability and number of perfect matchings

This page was built for publication: A determinant-based algorithm for counting perfect matchings in a general graph

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