An Extension of Complexity Bounds and Dynamic Heuristics for Tree-Decompositions of CSP

摘要

This paper deals with methods exploiting tree-decomposition approaches for solving constraint networks. We consider here the practical efficiency of these approaches by defining five classes of variable orders more and more dynamic which guarantee time complexity bounds from O(exp(w + 1)) to O(exp(2(w + k))), with w the "tree-width" of a CSP and k a constant. Finally, we assess practically their relevance.