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.009MaRDI QIDQ1704571zbMATH OpenOpenAlexFDO

Authors Christian Schridde

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

zbMATH Keywords

perfect matchingsplanar graphpermanentbipartite double covercounting satisfying solutions

Mathematics Subject Classification ID

Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) 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) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Recommendations

• The complexity of counting in sparse, regular, and planar graphs
• Computational complexity of counting problems on 3-regular planar graphs
• The Complexity of Planar Counting Problems
• A bottom-up algorithm for solving \#2SAT
• Theory and Applications of Models of Computation

Cites work

• scientific article; zbMATH DE number 4062621 (Why is no real title available?)
• scientific article; zbMATH DE number 845842 (Why is no real title available?)
• scientific article; zbMATH DE number 3259770 (Why is no real title available?)
• A polynomial-time approximation algorithm for the permanent of a matrix with nonnegative entries.
• A quadratic identity for the number of perfect matchings of plane graphs
• Algorithms for propositional model counting
• Circular planar graphs and resistor networks
• Complexity of generalized satisfiability counting problems
• Complexity of the Cover Polynomial
• Counting the number of perfect matchings in \(K_{5}\)-free graphs
• Dimer problem in statistical mechanics-an exact result
• Holographic Algorithms
• Holographic algorithms with matchgates capture precisely tractable planar \#CSP
• NP is as easy as detecting unique solutions
• Paths, Trees, and Flowers
• Planar Formulae and Their Uses
• Planarizing Gadgets for Perfect Matching Do Not Exist
• The Complexity of Planar Counting Problems
• The complexity of computing the permanent
• The complexity of satisfiability problems
• The statistics of dimers on a lattice. I: The number of dimer arrangements on a quadratic lattice
• Über eine Eigenschaft der ebenen Komplexe

Cited in

(1)

• Theory and Applications of Models of Computation

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

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