As a guest user you are not logged in or recognized by your IP address. You have
access to the Front Matter, Abstracts, Author Index, Subject Index and the full
text of Open Access publications.
Shaving algorithms, like singleton arc consistency (SAC), are currently receiving much interest. They remove values which are not part of any solution. This paper proposes an efficient shaving algorithm for enforcing stronger forms of consistency than SAC. The algorithm is based on the notion of weak k-singleton arc consistency, which is equal to sac if k=1 but stronger if k>1. This paper defines the notion, explains why it is useful, and presents an algorithm for enforcing it. The algorithm generalises Lecoutre and Cardon's algorithm for establishing sac. Used as pre-processor for MAC it improves the solution time for structured problems. When run standalone for k>1, it frequently removes more values than sac at a reasonable time. Our experimental results indicate that at the sac phase transition, it removes many more values than SAC-1 for k=16 in less time. For many problems from the literature the algorithm discovers lucky solutions. Frequently, it returns satisfiable csps which it proves inverse consistent if all values participate in a lucky solution.
This website uses cookies
We use cookies to provide you with the best possible experience. They also allow us to analyze user behavior in order to constantly improve the website for you. Info about the privacy policy of IOS Press.
This website uses cookies
We use cookies to provide you with the best possible experience. They also allow us to analyze user behavior in order to constantly improve the website for you. Info about the privacy policy of IOS Press.