Counting truth assignments of formulas of bounded tree-width or clique-width
From MaRDI portal
Recommendations
- On the Expressive Power of CNF Formulas of Bounded Tree- and Clique-Width
- On the expressive power of CNF formulas of bounded tree- and clique-width
- Model counting for formulas of bounded clique-width
- Counting and Enumeration Problems with Bounded Treewidth
- A Natural Generalization of Bounded Tree-Width and Bounded Clique-Width
- scientific article; zbMATH DE number 1830724
- Deciding Clique-Width for Graphs of Bounded Tree-Width
- Treewidth and counting projected answer sets
- Bounded Tree-Width and CSP-Related Problems
- A trichotomy theorem for the approximate counting of complex-weighted bounded-degree Boolean CSPs
Cites work
- Algorithmic uses of the Feferman-Vaught theorem
- All structured programs have small tree width and good register allocation
- Approximating clique-width and branch-width
- Colored Tutte polynomials and Kauffman brackets for graphs of bounded tree width
- Coloured Tutte polynomials and Kauffman brackets for graphs of bounded tree width
- Complexity classifications of Boolean constraint satisfaction problems
- Complexity of Finding Embeddings in a k-Tree
- Complexity of generalized satisfiability counting problems
- Evaluating the Tutte Polynomial for Graphs of Bounded Tree-Width
- Farrell polynomials on graphs of bounded tree width
- Fusion in relational structures and the verification of monadic second-order properties
- Handle-rewriting hypergraph grammars
- scientific article; zbMATH DE number 3639144 (Why is no real title available?)
- scientific article; zbMATH DE number 610968 (Why is no real title available?)
- scientific article; zbMATH DE number 1512682 (Why is no real title available?)
- scientific article; zbMATH DE number 1756016 (Why is no real title available?)
- scientific article; zbMATH DE number 1361465 (Why is no real title available?)
- scientific article; zbMATH DE number 3449757 (Why is no real title available?)
- scientific article; zbMATH DE number 809155 (Why is no real title available?)
- scientific article; zbMATH DE number 3313427 (Why is no real title available?)
- Logical description of context-free graph languages
- Many hard examples for resolution
- Monadic second-order evaluations on tree-decomposable graphs
- NCE graph grammars and clique-width.
- On generating all maximal independent sets
- On the clique-width of graph with few \(P_{4}\)'s
- On the clique-width of some perfect graph classes
- On the colored Tutte polynomial of a graph of bounded treewidth
- On the complexity of regular resolution and the Davis-Putnam procedure
- On the fixed parameter complexity of graph enumeration problems definable in monadic second-order logic
- Partition-based logical reasoning for first-order and propositional theories
- Polynomial Invariants of Graphs
- Recognizability, hypergraph operations, and logical types
- Satisfiability, branch-width and Tseitin tautologies
- Splitting formulas for Tutte polynomials
- The Complexity of Enumeration and Reliability Problems
- The complexity of first-order and monadic second-order logic revisited
- The complexity of satisfiability problems
- The Computational Structure of Monotone Monadic SNP and Constraint Satisfaction: A Study through Datalog and Group Theory
- The intractability of resolution
- The monadic second-order logic of graphs. VII: Graphs as relational structures
- The monadic second-order logic of graphs. XIV: Uniformly sparse graphs and edge set quantifica\-tions.
- Theory and Applications of Satisfiability Testing
- Theory and Applications of Satisfiability Testing
- Tree clustering for constraint networks
- Tree-width and the monadic quantifier hierarchy.
- Tutte polynomials computable in polynomial time
- Unification as a complexity measure for logic programming
- Upper bounds to the clique width of graphs
Cited in
(45)- An extension of the bivariate chromatic polynomial
- Weighted positive binary decision diagrams for exact probabilistic inference
- The complexity landscape of decompositional parameters for ILP
- Grammars and clique-width bounds from split decompositions
- On efficiently solvable cases of quantum \(k\)-SAT
- An extended tree-width notion for directed graphs related to the computation of permanents
- Algorithms for propositional model counting
- Bounded treewidth as a key to tractability of knowledge representation and reasoning
- The rank-width of edge-coloured graphs
- From tree-decompositions to clique-width terms
- Latency-bounded target set selection in social networks
- Solving \#SAT using vertex covers
- Using binary patterns for counting falsifying assignments of conjunctive forms
- Backdoors to q-Horn
- Model counting for formulas of bounded clique-width
- Backdoors to satisfaction
- Better algorithms for satisfiability problems for formulas of bounded rank-width
- Model counting for CNF formulas of bounded modular treewidth
- An extended tree-width notion for directed graphs related to the computation of permanents
- Satisfiability of acyclic and almost acyclic CNF formulas. II
- Characterizing Arithmetic Circuit Classes by Constraint Satisfaction Problems
- F-rank-width of (edge-colored) graphs
- Solving MaxSAT and \#SAT on structured CNF formulas
- Model counting for CNF formulas of bounded modular treewidth
- Algorithms for Propositional Model Counting
- Complexity and Algorithms for Well-Structured k-SAT Instances
- Variable Influences in Conjunctive Normal Forms
- Satisfiability of acyclic and almost acyclic CNF formulas
- The complexity of weighted counting for acyclic conjunctive queries
- Beating brute force for (quantified) satisfiability of circuits of bounded treewidth
- Multi-clique-width
- On efficiently solvable cases of quantum k-SAT
- Sum-of-Products with Default Values: Algorithms and Complexity Results
- Tractable QBF by knowledge compilation
- Planar 3-SAT with a clause/variable cycle
- A Most General Edge Elimination Polynomial
- On the Expressive Power of CNF Formulas of Bounded Tree- and Clique-Width
- Solving #SAT Using Vertex Covers
- On the expressive power of CNF formulas of bounded tree- and clique-width
- Compact labelings for efficient first-order model-checking
- The enumeration of vertex induced subgraphs with respect to the number of components
- My writing
- Polynomial threshold functions of bounded tree-width: some explainability and complexity aspects
- Tensor network contractions for \#SAT
- Graph classes with and without powers of bounded clique-width
This page was built for publication: Counting truth assignments of formulas of bounded tree-width or clique-width
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2473047)
