ECAI-2002 Conference Paper

[full paper]

Combining hypertree, bicomp, and hinge decomposition

Georg Gottlob, Martin Hutle, Franz Wotawa

Solving Constraint Satisfaction Problems (CSP) is in general NP-complete. If the structure of the CSP is a tree, then the computation can be done very effectively in a backtrack-free manner. There are several methods for converting CSPs in their tree-structured equivalent, e.g., hinge decomposition. More recently hypertree decomposition was developed and proved to subsume all other previously developed structure-based decomposition methods. In this paper we report recent results of a hypertree-decomposition implementation. We further have combined hypertree decomposition, biconnected component decomposition (bicomp), hinge decomposition to improve running time and to make hypertree decomposition applicable on larger CSP instances. The formal requirements and the empirical results of the combined algorithms are reported.

Keywords: Constraint Satisfaction, Search

Citation: Georg Gottlob, Martin Hutle, Franz Wotawa: Combining hypertree, bicomp, and hinge decomposition. In F. van Harmelen (ed.): ECAI2002, Proceedings of the 15th European Conference on Artificial Intelligence, IOS Press, Amsterdam, 2002, pp.161-165.