On the expressive power of CNF formulas of bounded tree- and clique-width
From MaRDI portal
Publication:617890
DOI10.1016/J.DAM.2010.09.007zbMATH Open1207.05093OpenAlexW2117939403MaRDI QIDQ617890FDOQ617890
Authors: Irenée Briquel, Pascal Koiran, Klaus Meer 
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
Recommendations
- On the Expressive Power of CNF Formulas of Bounded Tree- and Clique-Width
- Counting truth assignments of formulas of bounded tree-width or clique-width
- Bounded Tree-Width and CSP-Related Problems
- Constraint Satisfaction with Bounded Treewidth Revisited
- Constraint satisfaction with bounded treewidth revisited
- Constraint Satisfaction, Bounded Treewidth, and Finite-Variable Logics
- Extended formulation for CSP that is compact for instances of bounded treewidth
- scientific article; zbMATH DE number 1830724
- A Natural Generalization of Bounded Tree-Width and Bounded Clique-Width
- Bounded tree-width and LOGCFL
conjunctive normal form formulasexpressive power of polynomialspermanent functiontree- and clique-widthValiant's complexity theory for polynomial families
Cites Work
- Counting truth assignments of formulas of bounded tree-width or clique-width
- Communication Complexity
- Some Exact Complexity Results for Straight-Line Computations over Semirings
- Parallel Algorithms with Optimal Speedup for Bounded Treewidth
- On the fixed parameter complexity of graph enumeration problems definable in monadic second-order logic
- On the Expressive Power of Planar Perfect Matching and Permanents of Bounded Treewidth Matrices
- Tree-width, path-width, and cutwidth
- Title not available (Why is that?)
- Algorithms for Propositional Model Counting
- On the Expressive Power of CNF Formulas of Bounded Tree- and Clique-Width
- Characterizing Valiant’s Algebraic Complexity Classes
Cited In (14)
- The complexity of weighted counting for acyclic conjunctive queries
- On the expressive power of permanents and perfect matchings of matrices of bounded pathwidth/cliquewidth
- Tree-width in algebraic complexity
- On the Expressive Power of CNF Formulas of Bounded Tree- and Clique-Width
- An extended tree-width notion for directed graphs related to the computation of permanents
- An extended tree-width notion for directed graphs related to the computation of permanents
- Graph width measures for CNF-encodings with auxiliary variables
- Counting truth assignments of formulas of bounded tree-width or clique-width
- Revisiting graph width measures for CNF-encodings
- Lower Bounds for Width-Restricted Clause Learning on Small Width Formulas
- Algebraic complexity classes
- Characterizing Arithmetic Circuit Classes by Constraint Satisfaction Problems
- On extremal \(k\)-CNF formulas
- A Stronger LP Bound for Formula Size Lower Bounds via Clique Constraints
This page was built for publication: On the expressive power of CNF formulas of bounded tree- and clique-width
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q617890)
