Abstract:

Based on det-k-decomp algorithm, along with the noting  isomorphic component and reducing the search space for an appropriate separator, the authors  presented a new class of hypertree decomposition: separated hypertree decomposition and presented a new tractable hypertree decomposition algorithm——sht-k-decomp, which can improve the efficiency of constrain satisfaction problem solving effectively. The experimental results on most instances show that our method outperforms det-k-decomp.

Key words: artificial intelligence, hypertree decomposition, constraint satisfaction problems