An optimal k-consistency algorithm

摘要

This paper generalizes the arc-consistency algorithm of Mohr and Henderson [4] and the path-consistency algorithm of Han and Lee [2] to a k-consistency algorithm (arc-consistency and path-consistency being 2-consistency and 3-consistency, respectively). The algorithm is a development of Freuder's synthesis algorithm [1]. It simultaneously establishes i-consistency for each 1 ⩽ i ⩽ k. It has worst-case time and space complexity which is optimal when k is a constant and almost optimal for all other values of k.In the case that all order-i constraints exist for all 1 ⩽ i ⩽ n, this algorithm is a solution to the consistent labeling problem with almost optimal worst-case time and space complexity.