Counting models for 2SAT and 3SAT formulae

2004/11/18 by Vilhelm Dahllöf, Peter Jonsson, Peter Jönsson +1 · 4 citations
Computer Science · Mathematics · #Advanced Graph Theory Research #Algorithm #Boolean satisfiability problem #Combinatorics #Complexity and Algorithms in Graphs #Computational complexity theory #Computer science #Data Management and Algorithms #Discrete mathematics #Mathematics #PSPACE #Polynomial #Satisfiability #Separable space #Time complexity #True quantified Boolean formula

paper · pdf · doi:10.1016/j.tcs.2004.10.037

openalex publication_date 2004/11/18 · crossref created 2004/11/18 · crossref issued 2005/02/01 · crossref published 2005/02/01 · crossref published-print 2005/02/01 · crossref deposited 2025/10/05 · openalex created_date 2025/10/10 · crossref indexed 2026/06/03 · openalex updated_date 2026/07/31

Citations

• The Design and Analysis of Algorithms
• The complexity of computing the permanent
• A partial k-arboretum of graphs with bounded treewidth
• Finding a Maximum Independent Set
• The Complexity of Enumeration and Reliability Problems

Cited by

• A Tighter Bound for Counting Max-Weight Solutions to 2SAT Instances
• Algorithms for the Maximum Hamming Distance Problem
• Algorithms for Counting 2-Sat Solutions and Colorings with Applications
• 2-satisfiability [wikipedia]