@inproceedings{d00f25b5ac1c4c1d943c3628893caaab,
title = "Understanding and improving the MAC algorithm",
abstract = "Constraint satisfaction problems have wide application in artificial intelligence. They involve finding values for problem variables where the values must be consistent in that they satisfy restrictions on which combinations of values are allowed. Recent research on finite domain constraint satisfaction problems suggest that Maintaining Arc Consistency (MAC) is the most efficient general CSP algorithm for solving large and hard problems. In the first part of this paper we explain why maintaining full, as opposed to limited, arc consistency during search can greatly reduce the search effort. Based on this explanation, in the second part of the paper we show how to modify MAC in order to make it even more efficient. Experimental results prove that the gain in efficiency can be quite important.",
author = "Daniel Sabin and Freuder, \{Eugene C.\}",
note = "Publisher Copyright: {\textcopyright} Springer-Verlag Berlin Heidelberg 1997.; 3rd International Conference on Principles and Practice of Constraint Programming, CP 1997 ; Conference date: 29-10-1997 Through 01-11-1997",
year = "1997",
doi = "10.1007/bfb0017438",
language = "English",
isbn = "3540637532",
series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",
publisher = "Springer Verlag",
pages = "167--181",
editor = "Gert Smolka",
booktitle = "Principles and Practice of Constraint Programming - CP 1997 - 3rd International Conference, CP 1997, Proceedings",
address = "Germany",
}