Dynamic Heuristics for Backtrack Search on Tree-Decomposition of CSPs
Abstract
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 preserve the time complexity bound. For that, we define extensions of this theoretical time complexity bound to increase the dynamic aspect of these orders. We define a constant k allowing us to extend the classical bound from O(exp(w+1)) firstly to O(exp(w+k+1)), and finally to O(exp(2(w+k+1)-s - )), with w the "tree-width" of a CSP and s - the minimum size of its separators. Finally, we assess the defined theoretical extension of the time complexity bound from a practical viewpoint.
Cite
Text
Jégou et al. "Dynamic Heuristics for Backtrack Search on Tree-Decomposition of CSPs." International Joint Conference on Artificial Intelligence, 2007.Markdown
[Jégou et al. "Dynamic Heuristics for Backtrack Search on Tree-Decomposition of CSPs." International Joint Conference on Artificial Intelligence, 2007.](https://mlanthology.org/ijcai/2007/jegou2007ijcai-dynamic/)BibTeX
@inproceedings{jegou2007ijcai-dynamic,
title = {{Dynamic Heuristics for Backtrack Search on Tree-Decomposition of CSPs}},
author = {Jégou, Philippe and Ndiaye, Samba and Terrioux, Cyril},
booktitle = {International Joint Conference on Artificial Intelligence},
year = {2007},
pages = {112-117},
url = {https://mlanthology.org/ijcai/2007/jegou2007ijcai-dynamic/}
}