The complexity of weighted and unweighted #CSP
The complexity of weighted and unweighted #CSP
复制标题
DOI：
10.1016/j.jcss.2011.12.002
复制
发表时间：
2010-05
期刊：
影响因子：
--
通讯作者：
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
我们给一些减少问题（非负）加权#CSP限制类的功能，需要考虑在计算复杂性的研究。我们的减少可以应用于精确和近似计算。特别是，我们表明，最近的二分法未加权#CSP可以扩展到有理加权#CSP。
We give some reductions among problems in (nonnegative) weighted #CSP which restrict the class of functions that needs to be considered in computational complexity studies. Our reductions can be applied to both exact and approximate computation. In particular, we show that the recent dichotomy for unweighted #CSP can be extended to rational-weighted #CSP.