Alternative algorithms for counting all matchings in graphs

DOI10.1007/3-540-36494-3_38MaRDI QIDQ4418670zbMATH OpenFDO

Authors Piotr Sankowski

Publication date 11 August 2003

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL http://link.springer.de/link/service/series/0558/bibs/2607/26070427.htm

zbMATH Keywords

Godman-Godsil estimatorMarkov chainrandom graphs

Mathematics Subject Classification ID

Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Random graphs (graph-theoretic aspects) (05C80) Graph algorithms (graph-theoretic aspects) (05C85)

Recommendations

• Counting matchings in graphs
• The computational strength of matchings in countable graphs
• Algorithms for enumerating all perfect, maximum and maximal matchings in bipartite graphs
• A determinant-based algorithm for counting perfect matchings in a general graph
• scientific article; zbMATH DE number 4051678
• Matchings in Graphs Variations of the Problem
• On counting perfect matchings in general graphs
• On matchings in graphs
• Graphical condensation for enumerating perfect matchings
• Efficient algorithms for finding maximum matching in graphs

Cited in

(6)

• On counting 3-D matchings of size \(k\)
• Sequential Monte Carlo for counting vertex covers in general graphs
• A determinant-based algorithm for counting perfect matchings in a general graph
• Counting perfect matchings as fast as Ryser
• Sequential importance sampling for estimating expectations over the space of perfect matchings
• Multivariable goodness tests and approximation of the residues of quadratic forms

This page was built for publication: Alternative algorithms for counting all matchings in graphs

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