Model Counting for Formulas of Bounded Clique-Width
Model Counting for Formulas of Bounded Clique-Width
复制标题
有界团宽度公式的模型计数
DOI：
--
复制
发表时间：
2013
期刊：
影响因子：
--
通讯作者：
Stefan Szeider
中科院分区：
文献类型：
--
作者：
Friedrich Slivovsky;Stefan Szeider
我们表明，#SAT是多项式时间听话的类CNF公式的关联图有界对称的ck-width（或有界ck-width，或有界秩宽度）。这一结果严格推广了多项式时间易处理性的结果与符号关联图的有界树宽的公式类和公式类的关联图的有界模树宽，这是迄今为止已知的最一般的结果。
We show that #SAT is polynomial-time tractable for classes of CNF formulas whose incidence graphs have bounded symmetric clique-width (or bounded clique-width, or bounded rank-width). This result strictly generalizes polynomial-time tractability results for classes of formulas with signed incidence graphs of bounded clique-width and classes of formulas with incidence graphs of bounded modular treewidth, which were the most general results of this kind known so far.