Counting the number of perfect matchings in \(K_{5}\)-free graphs
From MaRDI portal
Publication:503455
DOI10.1007/s00224-015-9645-1zbMath1353.05100OpenAlexW2466240783MaRDI QIDQ503455
Thomas Thierauf, Fabian Wagner, Simon Straub
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
Enumeration in graph theory (05C30) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)
Related Items (6)
Unnamed Item ⋮ On the construction of graphs with a planar bipartite double cover from Boolean formulas and its application to counting satisfying solutions ⋮ Connectivity and some other properties of generalized Sierpiński graphs ⋮ Counting the number of perfect matchings, and generalized decision trees ⋮ Planar Maximum Matching: Towards a Parallel Algorithm ⋮ NC Algorithms for Computing a Perfect Matching and a Maximum Flow in One-Crossing-Minor-Free Graphs
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- The complexity of computing the permanent
- NC algorithms for computing the number of perfect matchings in \(K_{3,3}\)-free graphs and related problems
- A new graph triconnectivity algorithm and its parallelization
- On the computation of pfaffians
- Incremental convex planarity testing
- Approximation algorithms for classes of graphs excluding single-crossing graphs as minors
- The combinatorial approach yields an NC algorithm for computing Pfaffians
- On-line maintenance of triconnected components with SPQR-trees
- A V log V algorithm for isomorphism of triconnected planar graphs
- Graph Isomorphism for K_{3, 3}-free and K_5-free graphs is in Log-space.
- Holographic Algorithms
- Paths, Trees, and Flowers
This page was built for publication: Counting the number of perfect matchings in \(K_{5}\)-free graphs
