On the expressive power of CNF formulas of bounded tree- and clique-width
From MaRDI portal
Publication:617890
DOI10.1016/j.dam.2010.09.007zbMath1207.05093OpenAlexW2117939403MaRDI QIDQ617890
Irenée Briquel, Klaus Meer, Pascal Koiran
Publication date: 14 January 2011
Published in: Discrete Applied Mathematics (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.dam.2010.09.007
conjunctive normal form formulasexpressive power of polynomialspermanent functiontree- and clique-widthValiant's complexity theory for polynomial families
Related Items (5)
The complexity of weighted counting for acyclic conjunctive queries ⋮ An Extended Tree-Width Notion for Directed Graphs Related to the Computation of Permanents ⋮ Characterizing Arithmetic Circuit Classes by Constraint Satisfaction Problems ⋮ An extended tree-width notion for directed graphs related to the computation of permanents ⋮ Algebraic Complexity Classes
Cites Work
- Unnamed Item
- Tree-width, path-width, and cutwidth
- Counting truth assignments of formulas of bounded tree-width or clique-width
- Algorithms for Propositional Model Counting
- Some Exact Complexity Results for Straight-Line Computations over Semirings
- Parallel Algorithms with Optimal Speedup for Bounded Treewidth
- Communication Complexity
- On the Expressive Power of CNF Formulas of Bounded Tree- and Clique-Width
- On the Expressive Power of Planar Perfect Matching and Permanents of Bounded Treewidth Matrices
- Characterizing Valiant’s Algebraic Complexity Classes
- On the fixed parameter complexity of graph enumeration problems definable in monadic second-order logic
This page was built for publication: On the expressive power of CNF formulas of bounded tree- and clique-width
