Counting the number of perfect matchings in K₅-free graphs
From MaRDI portal
Publication:503455
DOI10.1007/S00224-015-9645-1zbMATH Open1353.05100OpenAlexW2466240783MaRDI QIDQ503455FDOQ503455
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
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
Enumeration in graph theory (05C30) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)
Cites Work
- Paths, Trees, and Flowers
- Title not available (Why is that?)
- Title not available (Why is that?)
- The complexity of computing the permanent
- Holographic Algorithms
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- Graph isomorphism for \(K_{3,3}\)-free and \(K_5\)-free graphs is in Log-space
- Title not available (Why is that?)
- On-line maintenance of triconnected components with SPQR-trees
- The combinatorial approach yields an NC algorithm for computing Pfaffians
- Some perfect matchings and perfect half-integral matchings in NC
- Approximation algorithms for classes of graphs excluding single-crossing graphs as minors
- Title not available (Why is that?)
- A new graph triconnectivity algorithm and its parallelization
- 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
- A V log V algorithm for isomorphism of triconnected planar graphs
- Reachability in \(K_{3,3}\)-free and \(K_5\)-free graphs is in unambiguous logspace
Cited In (7)
- 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
- Title not available (Why is that?)
- 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
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)
