On the construction of graphs with a planar bipartite double cover from Boolean formulas and its application to counting satisfying solutions
DOI10.1016/j.tcs.2017.11.009zbMath1388.68240OpenAlexW2770870172MaRDI QIDQ1704571
Publication date: 12 March 2018
Published in: Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.tcs.2017.11.009
Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Planar graphs; geometric and topological aspects of graph theory (05C10) Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Counting the number of perfect matchings in \(K_{5}\)-free graphs
- The complexity of computing the permanent
- NP is as easy as detecting unique solutions
- Circular planar graphs and resistor networks
- Complexity of generalized satisfiability counting problems
- Algorithms for propositional model counting
- A quadratic identity for the number of perfect matchings of plane graphs
- Über eine Eigenschaft der ebenen Komplexe
- The statistics of dimers on a lattice
- Planarizing Gadgets for Perfect Matching Do Not Exist
- A polynomial-time approximation algorithm for the permanent of a matrix with nonnegative entries
- Holographic Algorithms
- Planar Formulae and Their Uses
- The Complexity of Planar Counting Problems
- Dimer problem in statistical mechanics-an exact result
- Paths, Trees, and Flowers
- The complexity of satisfiability problems
- Complexity of the Cover Polynomial
- Holographic Algorithms with Matchgates Capture Precisely Tractable Planar #CSP
This page was built for publication: On the construction of graphs with a planar bipartite double cover from Boolean formulas and its application to counting satisfying solutions
