Counting the number of perfect matchings in K₅-free graphs

DOI10.1007/S00224-015-9645-1MaRDI QIDQ503455zbMATH OpenOpenAlexFDO

Authors Simon Straub, Thomas Thierauf, Fabian Wagner

Publication date 12 January 2017

Published in Theory of Computing Systems (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/s00224-015-9645-1

zbMATH Keywords

complexitycountingperfect matching

Mathematics Subject Classification ID

Enumeration in graph theory (05C30) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Recommendations

• scientific article; zbMATH DE number 4062621
• NC algorithms for computing the number of perfect matchings in \(K_{3,3}\)-free graphs and related problems
• scientific article; zbMATH DE number 6002056
• The enumeration of perfect matchings in two types of graphs
• Counting the number of perfect matchings, and generalized decision trees

Cites work

• scientific article; zbMATH DE number 43583 (Why is no real title available?)
• scientific article; zbMATH DE number 3517179 (Why is no real title available?)
• scientific article; zbMATH DE number 475621 (Why is no real title available?)
• scientific article; zbMATH DE number 1161568 (Why is no real title available?)
• scientific article; zbMATH DE number 3236772 (Why is no real title available?)
• scientific article; zbMATH DE number 3290993 (Why is no real title available?)
• scientific article; zbMATH DE number 3326387 (Why is no real title available?)
• A V log V algorithm for isomorphism of triconnected planar graphs
• A new graph triconnectivity algorithm and its parallelization
• Approximation algorithms for classes of graphs excluding single-crossing graphs as minors
• Graph isomorphism for \(K_{3,3}\)-free and \(K_5\)-free graphs is in Log-space
• Holographic Algorithms
• Incremental convex planarity testing
• NC algorithms for computing the number of perfect matchings in \(K_{3,3}\)-free graphs and related problems
• On the computation of pfaffians
• On-line maintenance of triconnected components with SPQR-trees
• Paths, Trees, and Flowers
• Reachability in \(K_{3,3}\)-free and \(K_5\)-free graphs is in unambiguous logspace
• Some perfect matchings and perfect half-integral matchings in NC
• The combinatorial approach yields an NC algorithm for computing Pfaffians
• The complexity of computing the permanent

Cited in

(7)

• Connectivity and some other properties of generalized Sierpiński graphs
• Counting problems in parameterized complexity
• NC algorithms for computing a perfect matching and a maximum flow in one-crossing-minor-free graphs
• Counting the number of perfect matchings, and generalized decision trees
• Planar Maximum Matching: Towards a Parallel Algorithm
• scientific article; zbMATH DE number 6274837 (Why is no real title available?)
• On the construction of graphs with a planar bipartite double cover from Boolean formulas and its application to counting satisfying solutions

This page was built for publication: Counting the number of perfect matchings in \(K_{5}\)-free graphs

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