Thumbnail
Access Restriction
Subscribed

Author Naanaa, Wady
Source ACM Digital Library
Content type Text
Publisher Association for Computing Machinery (ACM)
File Format PDF
Copyright Year ©2009
Language English
Subject Domain (in DDC) Computer science, information & general works ♦ Computer programming, programs & data
Subject Keyword Constraint graph orientation ♦ Constraint satisfaction problems ♦ Domain decomposition algorithms ♦ Value substitutability
Abstract This article presents a domain decomposition algorithm for solving constraint satisfactions problems (CSPs). The proposed algorithm relies on a weak form of neighborhood substitutability referred to as directional substitutability. The main idea is that although two values may not be neighborhood substitutable if we consider the whole neighborhood of a given variable, they could be substitutable if we only focus on a part of the neighborhood induced by an orientation of the constraint graph. Directional substitutability provides a mean to decompose value domains into chains of directionally substitutable values that can be attempted simultaneously during search. We report experiments carried out on several binary CSPs which clearly indicate that variations of classical algorithms which exploit directional substitutability often outperform the original algorithms.
ISSN 10846654
Age Range 18 to 22 years ♦ above 22 year
Educational Use Research
Education Level UG and PG
Learning Resource Type Article
Publisher Date 2009-02-01
Publisher Place New York
e-ISSN 10846654
Journal Journal of Experimental Algorithmics (JEA)
Volume Number 13
Page Count 11
Starting Page 1.13
Ending Page 1.23


Open content in new tab

   Open content in new tab
Source: ACM Digital Library