Understanding Model Counting for beta-acyclic CNF-formulas
Understanding Model Counting for beta-acyclic CNF-formulas
复制标题
了解 β-无环 CNF 公式的模型计数
DOI：
10.4230/lipics.stacs.2015.143
复制
发表时间：
2014
期刊：
影响因子：
--
通讯作者：
S. Mengel
中科院分区：
文献类型：
--
作者：
Johann Brault;Florent Capelli;S. Mengel
我们通过给出 $\beta$-非循环 $\mathrm{\#SAT}$ 的多项式时间算法来扩展关于 $\mathrm{\#SAT}$ 的所谓结构限制的知识。与该领域以前的算法相比，我们的算法不是通过动态规划进行，而是按照消除顺序工作，求解约束满足的加权版本。此外，我们证明这种与更标准算法的偏差并非巧合，而是可能不存在 $\beta$-非循环 $\mathrm{\#SAT}$ 通常风格的动态规划算法。
We extend the knowledge about so-called structural restrictions of $\mathrm{\#SAT}$ by giving a polynomial time algorithm for $\beta$-acyclic $\mathrm{\#SAT}$. In contrast to previous algorithms in the area, our algorithm does not proceed by dynamic programming but works along an elimination order, solving a weighted version of constraint satisfaction. Moreover, we give evidence that this deviation from more standard algorithm is not a coincidence, but that there is likely no dynamic programming algorithm of the usual style for $\beta$-acyclic $\mathrm{\#SAT}$.
DOI：
10.1016/j.jcss.2011.12.002
发表时间：
2010-05
期刊：
J. Comput. Syst. Sci.
影响因子：
--
作者：
A. Bulatov;M. Dyer;L. A. Goldberg;Markus Jalsenius;M. Jerrum;David Richerby
通讯作者：
A. Bulatov;M. Dyer;L. A. Goldberg;Markus Jalsenius;M. Jerrum;David Richerby