Skip to Main content Skip to Navigation
Reports

A Correct Path Consistency Algorithm and An Optimal Generalized Arc Consistency Algorithm

Abstract : This paper presents a careful construction of a correct version of the path consistency algorithm published in (Moh-86). The same kind of construction is then used to extend the optimal arc consistency algorithm AC4 into GAC4 for n-ary constraints. Furthermore an evaluation technic is provided which evaluates the algorithm on the basis of the size of the constraints. It is proven that both AC4 and its extension are linear in the size of the constraints and therefore are optimal.
Complete list of metadata

https://hal.inria.fr/inria-00548481
Contributor : Thoth Team <>
Submitted on : Monday, December 20, 2010 - 8:49:36 AM
Last modification on : Friday, February 26, 2021 - 3:26:01 PM

Identifiers

  • HAL Id : inria-00548481, version 1

Collections

Citation

Roger Mohr. A Correct Path Consistency Algorithm and An Optimal Generalized Arc Consistency Algorithm. [Research Report] 87-R-030, 1987. ⟨inria-00548481⟩

Share

Metrics

Record views

66