Title :
Arc-Consistency in Constraint Satisfaction Problems: A Survey
Author :
Dib, Mohammad ; Abdallah, Rouwaida ; Caminada, Alexandre
Author_Institution :
SET, UTBM, Belfort, France
Abstract :
Arc consistency (AC) is very important in Constraint Satisfaction Problems (CSPs). Several algorithms have been made to deal with arc consistency, the most known is the Maintaining arc consistency algorithm (MAC). The usefulness of AC processing was recognized early. As a result, many AC algorithms for binary constraints have been proposed in the literature. In this paper we will clearly present the most famous ones (AC-1, AC-2, AC-3, AC-4, AC-5, AC-6, AC-7, AC-2000, AC-2001, AC-inference). A comparative analysis is presented to figure out which one is the best to use.
Keywords :
constraint theory; graph colouring; operations research; AC-1 algorithm; AC-2 algorithm; AC-2000 algorithm; AC-2001 algorithm; AC-3 algorithm; AC-4 algorithm; AC-5 algorithm; AC-6 algorithm; AC-7 algorithm; AC-inference algorithm; constraint satisfaction problems; maintaining arc consistency algorithm; Arc Consistency; Constraints Satisfaction Problem (CSP); Search algorithm; constraints propagation;
Conference_Titel :
Computational Intelligence, Modelling and Simulation (CIMSiM), 2010 Second International Conference on
Conference_Location :
Bali
Print_ISBN :
978-1-4244-8652-6
Electronic_ISBN :
978-0-7695-4262-1
DOI :
10.1109/CIMSiM.2010.18
