Broken triangles: From value merging to a tractable class of general-arity constraint satisfaction problems
Broken triangles: From value merging to a tractable class of general-arity constraint satisfaction problems
复制标题
DOI：
10.1016/j.artint.2016.02.001
复制
发表时间：
2016-05
期刊：
影响因子：
--
通讯作者：
Martin C. Cooper;Aymeric Duchein;Achref El Mouelhi;Guillaume Escamocher;C. Terrioux;B. Zanuttini
中科院分区：
文献类型：
--
作者：
Martin C. Cooper;Aymeric Duchein;Achref El Mouelhi;Guillaume Escamocher;C. Terrioux;B. Zanuttini
一个二进制CSP实例满足brokentriangle性质（BTP）可以在多项式时间内解决。不幸的是，在实践中，很少有实例满足BTP。我们表明，本地版本的BTP允许合并域值在二进制CSP，从而提供了一种新的多项式时间减少操作。对基准实例的实验表明，对于某些类别的问题，实例大小显着减少。我们表明，BTP合并可以推广到任意arity的约束的情况下。一个有方向的版本的一般性BTP，然后允许我们扩展BTP易处理类以前只定义为二进制CSP。
A binary CSP instance satisfying the brokentriangle property (BTP) can be solved in polynomial time. Unfortunately, in practice, few instances satisfy the BTP. We show that a local version of the BTP allows the merging of domain values in binary CSPs, thus providing a novel polynomial-time reduction operation. Experimental trials on benchmark instances demonstrate a significant decrease in instance size for certain classes of problems. We show that BTP-merging can be generalised to instances with constraints of arbitrary arity. A directional version of the general-arity BTP then allows us to extend the BTP tractable class previously defined only for binary CSP.