An optimal k-consistency algorithm.

*(English)*Zbl 0678.68058Summary: 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.

##### MSC:

68R10 | Graph theory (including graph drawing) in computer science |

68Q25 | Analysis of algorithms and problem complexity |

68W99 | Algorithms in computer science |

##### Keywords:

k-consistency algorithm; arc-consistency algorithm; path-consistency algorithm; consistent labeling problem
Full Text:
DOI

##### References:

[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.