Karim Boutaleb, Philippe Jégou, Cyril Terrioux
It was shown that constraint satisfaction problems (CSPs) with a low width can be solved effectively by structural methods. In particular, the BTD method which exploits the concepts of goods and nogoods makes it possible to solve efficiently difficult instances. However, the memory space required for the storage of these (no)goods may make difficult or impossible the resolution of certain problems. We propose here to represent goods and nogoods with Binary Decision Diagrams (BDD). BDDs are data structures which efficiently represent informations in a compact and canonical form. Then, the practical interest of this trade-off which allows to save space memory to the detriment of time is assessed.
Subjects: 15.2 Constraint Satisfaction; 15.7 Search
Submitted: May 17, 2006