Counting truth assignments of formulas of bounded tree-width or clique-width

DOI10.1016/j.dam.2006.06.020zbMath1131.68093MaRDI QIDQ2473047

Eldar Fischer, Johann A. Makowsky, Elena V. Ravve

Publication date: 26 February 2008

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.dam.2006.06.020

zbMATH Keywords

clique-width; tree-width; counting problems; satisfiability (SAT); fixed parameter tractable (FPT)

Mathematics Subject Classification ID

68Q25: Analysis of algorithms and problem complexity

68R10: Graph theory (including graph drawing) in computer science

68T20: Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.)

Related Items

A Most General Edge Elimination Polynomial, On the Expressive Power of CNF Formulas of Bounded Tree- and Clique-Width, An extension of the bivariate chromatic polynomial, Algorithms for propositional model counting, Bounded treewidth as a key to tractability of knowledge representation and reasoning, Solving \#SAT using vertex covers, Algorithms for Propositional Model Counting, Variable Influences in Conjunctive Normal Forms

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Satisfiability, branch-width and Tseitin tautologies
• Algorithmic uses of the Feferman-Vaught theorem
• Monadic second-order evaluations on tree-decomposable graphs
• Tutte polynomials computable in polynomial time
• The intractability of resolution
• On generating all maximal independent sets
• Tree clustering for constraint networks
• The monadic second-order logic of graphs. VII: Graphs as relational structures
• On the complexity of regular resolution and the Davis-Putnam procedure
• All structured programs have small tree width and good register allocation
• Splitting formulas for Tutte polynomials
• Logical description of context-free graph languages
• Farrell polynomials on graphs of bounded tree width
• Tree-width and the monadic quantifier hierarchy.
• Coloured Tutte polynomials and Kauffman brackets for graphs of bounded tree width
• The monadic second-order logic of graphs. XIV: Uniformly sparse graphs and edge set quantifica\-tions.
• The complexity of first-order and monadic second-order logic revisited
• Complexity of generalized satisfiability counting problems
• Upper bounds to the clique width of graphs
• Handle-rewriting hypergraph grammars
• Partition-based logical reasoning for first-order and propositional theories
• On the colored Tutte polynomial of a graph of bounded treewidth
• Approximating clique-width and branch-width
• Recognizability, hypergraph operations, and logical types
• Complexity Classifications of Boolean Constraint Satisfaction Problems
• Fusion in relational structures and the verification of monadic second-order properties
• Many hard examples for resolution
• Complexity of Finding Embeddings in a k-Tree
• Unification as a complexity measure for logic programming
• Polynomial Invariants of Graphs
• The Complexity of Enumeration and Reliability Problems
• The Computational Structure of Monotone Monadic SNP and Constraint Satisfaction: A Study through Datalog and Group Theory
• Evaluating the Tutte Polynomial for Graphs of Bounded Tree-Width
• ON THE CLIQUE–WIDTH OF GRAPH WITH FEW P₄'S
• ON THE CLIQUE-WIDTH OF SOME PERFECT GRAPH CLASSES
• Theory and Applications of Satisfiability Testing
• Theory and Applications of Satisfiability Testing
• The complexity of satisfiability problems
• Graph-Theoretic Concepts in Computer Science
• On the fixed parameter complexity of graph enumeration problems definable in monadic second-order logic