Binarisation for Valued Constraint Satisfaction Problems
Binarisation for Valued Constraint Satisfaction Problems
复制标题
有价值的约束满足问题的二值化
DOI：
10.1137/16m1088107
复制
发表时间：
2017
影响因子：
0.8
通讯作者：
Cohen D
中科院分区：
文献类型：
--
作者：
Cohen D
研究了将有值约束满足问题（vcsp）转化为二元约束满足问题的方法。首先，我们证明了标准对偶编码保留了捕获vcsp计算复杂性的代数性质的许多方面。其次，我们将csp的还原扩展到Bulín等人描述的二进制csp。方法第一版。科学。[j],[11]（2015）。这种约简建立了固定值约束语言上的vcsp在多项式时间上等同于固定有向图上的最小代价同态问题。
We study methods for transforming valued constraint satisfaction problems (VCSPs) tobinaryVCSPs. First, we show that the standarddualencoding preserves many aspects of the algebraic properties that capture the computational complexity of VCSPs. Second, we extend the reduction of CSPs to binary CSPs described by Bulín et al. [Log. Methods Comput. Sci., 11 (2015)] to VCSPs. This reduction establishes that VCSPs over a fixed valued constraint language are polynomial-time equivalent to minimum-cost homomorphism problems over a fixed digraph.
登录
查看更多内容
将约束问题更好地简化为有向图
DOI：
--
发表时间：
2014
期刊：
Log. Methods Comput. Sci.
影响因子：
--
作者：
Jakub Bulín;D. Delic;M. Jackson;T. Niven
通讯作者：
T. Niven
Sherali-Adams 放宽对于普通价值 CSP 的作用
DOI：
--
发表时间：
2016
期刊：
SIAM journal on computing (Print)
影响因子：
--
作者：
Johan Thapper;Stanislav Živný
通讯作者：
Stanislav Živný
影响因子：
1.6
作者：
Cohen D
通讯作者：
Cohen D
Maltsev 有向图具有多数多态性
DOI：
--
发表时间：
2009
期刊：
European journal of combinatorics (Print)
影响因子：
--
作者：
Alexandr Kazda
通讯作者：
Alexandr Kazda
关于有向图着色问题和树宽对偶性
DOI：
10.1016/j.ejc.2007.11.004
发表时间：
2005
期刊：
20th Annual IEEE Symposium on Logic in Computer Science (LICS' 05)
影响因子：
--
作者：
Albert Atserias
通讯作者：
Albert Atserias