On the Expressive Power of CNF Formulas of Bounded Tree- and Clique-Width

DOI10.1007/978-3-540-92248-3_23zbMath1198.68183OpenAlexW2137041971MaRDI QIDQ5302060

Klaus Meer, Pascal Koiran

Publication date: 20 January 2009

Published in: Graph-Theoretic Concepts in Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-540-92248-3_23

zbMATH Keywords

expressiveness of CNF polynomials of bounded tree-width

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph polynomials (05C31) Graph theory (including graph drawing) in computer science (68R10) Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50)

Related Items (2)

On the expressive power of CNF formulas of bounded tree- and clique-width ⋮ Characterizing Arithmetic Circuit Classes by Constraint Satisfaction Problems

Cites Work

• Unnamed Item
• Separating the eraser Turing machine classes \(L_ e\), \(NL_ e\), \(co- NL_ e\) and \(P_ e\)
• Linear time solvable optimization problems on graphs of bounded clique-width
• Counting truth assignments of formulas of bounded tree-width or clique-width
• Algorithms for Propositional Model Counting
• Branching Programs and Binary Decision Diagrams
• On the Expressive Power of Planar Perfect Matching and Permanents of Bounded Treewidth Matrices
• Treewidth in Verification: Local vs. Global

This page was built for publication: On the Expressive Power of CNF Formulas of Bounded Tree- and Clique-Width