Title :
A New Method for Computing Suitable Tree-Decompositions with Respect to Structured CSP Solving
Author :
Pinto, Cédric ; Terrioux, Cyril
Author_Institution :
LSIS, Univ. Paul Cezanne, Marseille
Abstract :
The tree-decomposition notion plays a central role in the frame of the structured CSP solving. On the one hand, it is exploited in many methods like tree-clustering, BTD or cyclic-clustering (CC). It then leads to theoretical time complexity bounds among the best ones. On the other hand, it is often used as a preliminary step for computing a hypertree-decomposition. Unfortunately, finding the best tree-decomposition is a NP-hard problem. So heuristic methods are classically used for computing tree-decompositions. They mostly rely on triangulations of graphs. Sometimes, this approach by triangulation can lead to a rough identification of the structure. Such a drawback can be avoided by considering a cutset such that the remaining problem corresponds to a set of tree-decompositions. In this article, from a cutset and the corresponding set of tree-decompositions, we propose a new method for computing a suitable tree-decomposition w.r.t. CSP solving. Thanks to this approach, we can exploit BTD on the resulting tree-decomposition instead of CC on the cutset and the corresponding set of tree-decompositions. Then, unlike CC, it allows to fully exploit the informations recorded during the search, what leads to avoid some redundancies in the search space. In practice, the first empirical results are very promising since BTD with a tree-decomposition computed with the proposed method outperforms BTD with a tree-decomposition based on triangulation and some other classical algorithms.
Keywords :
computational complexity; constraint theory; set theory; tree searching; trees (mathematics); BTD; NP-hard problem; cutset problem; cyclic-clustering; graph triangulation; heuristic method; hypertree-decomposition computation; rough structure identification; search space; structured CSP solving; time complexity bound; tree-clustering; Artificial intelligence; Constraint theory; Frequency; Large scale integration; NP-complete problem; NP-hard problem; Tree graphs; constraint satifaction; structural methods;
Conference_Titel :
Tools with Artificial Intelligence, 2008. ICTAI '08. 20th IEEE International Conference on
Conference_Location :
Dayton, OH
Print_ISBN :
978-0-7695-3440-4
DOI :
10.1109/ICTAI.2008.112