Dynamic Heuristics for Backtrack Search on Tree-Decomposition of CSPs
Proceedings of the Twentieth International Joint Conference on Artificial Intelligence. Pages 112-116.
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.
@inproceedings{ijcai2007p16,
title = {Dynamic Heuristics for Backtrack Search on Tree-Decomposition of CSPs},
author = {Jégou, Philippe and Ndiaye, Samba and Terrioux, Cyril},
booktitle = {Proceedings of the Twentieth International Joint Conference on
Artificial Intelligence, {IJCAI-07}},
publisher = {International Joint Conferences on Artificial Intelligence},
editor = {Ramon López de Mántaras},
pages = {112--116},
year = {2007},
url = {https://ijcai.org/proceedings/2007/16},
}
TY - CPAPER TI - Dynamic Heuristics for Backtrack Search on Tree-Decomposition of CSPs AU - Jégou, Philippe AU - Ndiaye, Samba AU - Terrioux, Cyril T2 - Proceedings of the Twentieth International Joint Conference on Artificial Intelligence, IJCAI-07 PB - International Joint Conferences on Artificial Intelligence PY - 2007 SP - 112 EP - 116 UR - https://ijcai.org/proceedings/2007/16 ER -Copied
Machine-readable versions of this paper, for tools and AI agents:
