On the construction of graphs with a planar bipartite double cover from Boolean formulas and its application to counting satisfying solutions
type: Item
instance of: scholarly article
title: On the construction of graphs with a planar bipartite double cover from Boolean formulas and its application to counting satisfying solutions
zbMATH Open document ID: 1388.68240
author: Christian Schridde
published in: Theoretical Computer Science
publication date: 2018-03-12T00:00:00Z
Mathematics Subject Classification ID: 68R10
Mathematics Subject Classification ID: 05C10
Mathematics Subject Classification ID: 05C50
Mathematics Subject Classification ID: 05C70
Mathematics Subject Classification ID: 68Q25
zbMATH DE Number: 6848998
zbMATH Keywords: planar graph
zbMATH Keywords: bipartite double cover
zbMATH Keywords: perfect matchings
zbMATH Keywords: permanent
zbMATH Keywords: counting satisfying solutions
MaRDI profile type: Publication
full work available at URL: j.tcs.2017.11.009
OpenAlex ID: W2770870172
cites work: The complexity of computing the permanent
cites work: Q4864429
cites work: Dimer problem in statistical mechanics-an exact result
cites work: The statistics of dimers on a lattice. I: The number of dimer arrangements on a quadratic lattice
cites work: Holographic Algorithms
cites work: Holographic Algorithms with Matchgates Capture Precisely Tractable Planar #CSP
cites work: The complexity of satisfiability problems
cites work: Complexity of generalized satisfiability counting problems
cites work: NP is as easy as detecting unique solutions
cites work: Complexity of the Cover Polynomial
cites work: Circular planar graphs and resistor networks
cites work: Paths, Trees, and Flowers
cites work: A polynomial-time approximation algorithm for the permanent of a matrix with nonnegative entries
cites work: Planar Formulae and Their Uses
cites work: Über eine Eigenschaft der ebenen Komplexe
cites work: Q5545841
cites work: A quadratic identity for the number of perfect matchings of plane graphs
cites work: Planarizing Gadgets for Perfect Matching Do Not Exist
cites work: Algorithms for propositional model counting
cites work: The Complexity of Planar Counting Problems
cites work: Q3796778
cites work: Counting the number of perfect matchings in \(K_{5}\)-free graphs
DOI: 10.1016/J.TCS.2017.11.009
description: scientific article; zbMATH DE number 6848998