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.009zbMATH Open1388.68240OpenAlexW2770870172MaRDI QIDQ1704571FDOQ1704571

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

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

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)

Cites Work

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

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)