On the expressive power of CNF formulas of bounded tree- and clique-width

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

zbMATH Keywords

conjunctive normal form formulasexpressive power of polynomialspermanent functiontree- and clique-widthValiant's complexity theory for polynomial families

Mathematics Subject Classification ID

Graph polynomials (05C31)

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