论文标题
加强社区替代
Strengthening neighbourhood substitution
论文作者
论文摘要
减少域是解决约束满意度问题（CSP）的重要工具。在二进制CSP中，如果存在另一个可以在每个约束中代替它的值，则邻里替代是消除值。我们表明，邻里替代的概念可以通过两种不同的方式加强，而不会增加时间复杂。我们还表明了理论上的结果，与邻里替代不同，找到这些新操作的最佳顺序是NP-HARD。
Domain reduction is an essential tool for solving the constraint satisfaction problem (CSP). In the binary CSP, neighbourhood substitution consists in eliminating a value if there exists another value which can be substituted for it in each constraint. We show that the notion of neighbourhood substitution can be strengthened in two distinct ways without increasing time complexity. We also show the theoretical result that, unlike neighbourhood substitution, finding an optimal sequence of these new operations is NP-hard.
