Counting models for 2SAT and 3SAT formulae

DOI10.1016/j.tcs.2004.10.037zbMath1070.68050OpenAlexW2139364539WikidataQ56288403 ScholiaQ56288403MaRDI QIDQ1770390

Magnus Wahlström, Vilhelm Dahllöf, Peter Jonsson

Publication date: 6 April 2005

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2004.10.037

zbMATH Keywords

SatisfiabilityCounting modelsUpper boundsExact algorithmsExponential-time algorithms

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25)

Related Items

An enumerative algorithm for \#2SAT ⋮ Counting Maximal Independent Sets in Subcubic Graphs ⋮ A Method for Computing the Merrifield–Simmons Index on Benzenoid Systems ⋮ New upper bound for the \#3-SAT problem ⋮ A Tighter Bound for Counting Max-Weight Solutions to 2SAT Instances ⋮ Linear-programming design and analysis of fast algorithms for Max 2-CSP ⋮ Fast algorithms for max independent set ⋮ On independent sets and bicliques in graphs ⋮ Exact algorithms for maximum weighted independent set on sparse graphs (extended abstract) ⋮ Mass Customization and “Forecasting Options’ Penetration Rates Problem” ⋮ Rényi entropies as a measure of the complexity of counting problems ⋮ Faster exponential-time algorithms for approximately counting independent sets ⋮ Exact algorithms for minimum weighted dominating induced matching ⋮ Solving NP-Complete Problems with Quantum Search ⋮ Using binary patterns for counting falsifying assignments of conjunctive forms ⋮ О методах оценивания веса булевых биюнктивных функций ⋮ Faster graph coloring in polynomial space ⋮ Counting Independent Sets in Claw-Free Graphs ⋮ The union of minimal hitting sets: parameterized combinatorial bounds and counting

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• The complexity of computing the permanent
• Number of models and satisfiability of sets of clauses
• A partial k-arboretum of graphs with bounded treewidth
• Counting \(H-\)colorings of partial \(k-\)trees
• New methods for 3-SAT decision and worst-case analysis
• Counting the number of solutions for instances of satisfiability
• The Complexity of Counting in Sparse, Regular, and Planar Graphs
• The Complexity of Enumeration and Reliability Problems
• A Separator Theorem for Planar Graphs
• Linear Algorithms for Partitioning Embedded Graphs of Bounded Genus
• A Computing Procedure for Quantification Theory
• Principles and Practice of Constraint Programming – CP 2003