An optimal k-consistency algorithm. (English) Zbl 0678.68058

Summary: We generalize the arc-consistency algorithm of R. Mohr and T. C. Henderson [Artif. Intell. 28, 225-233 (1986)] and the path- consistency algorithm of C. C. Han and C.-H. Lee [Artif. Intell. 36, 125-130 (1988)] to a k-consistency algorithm (arc-consistency and path-consistency being 2-consistency and 3-consistency, respectively). The algorithm is a development of E. C. Freuder’s synthesis algorithm [Commun. ACM 21, 958-966 (1978; Zbl 0386.68065)]. It simultaneously establishes i-consistency for each \(1\leq i\leq 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\leq i\leq n\), this algorithm is a solution to the consistent labeling problem with almost optimal worst- case time and space complexity.


68R10 Graph theory (including graph drawing) in computer science
68Q25 Analysis of algorithms and problem complexity
68W99 Algorithms in computer science


Zbl 0386.68065
Full Text: DOI


[1] Freuder, E.C., Synthesizing constraint expressions, Commun. ACM, 21, 958-966, (1978) · Zbl 0386.68065
[2] Han, C.-C.; Lee, C.-H., Comments on mohr and Henderson’s path consistency algorithm, Artificial intelligence, 36, 125-130, (1988) · Zbl 0709.68534
[3] Mackworth, A.K., Consistency in networks of relations, Artificial intelligence, 8, 99-118, (1977) · Zbl 0341.68061
[4] Mohr, R.; Henderson, T.C., Arc and path consistency revisited, Artificial intelligence, 28, 225-233, (1986)
[5] Montanari, U., Networks of constraints: fundamental properties and applications to picture processing, Inform. sci., 7, 95-132, (1974) · Zbl 0284.68074
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.