Backtracking Procedures for Hypertree, HyperSpread and Connected Hypertree Decomposition of CSPs
Proceedings of the Twentieth International Joint Conference on Artificial Intelligence. Pages 180-184.
Abstract
Hypertree decomposition has been shown to be the most general CSP decomposition method. However, so far the exact methods are not able to find optimal hypertree decompositions of realistic instances. We present a backtracking procedure which, along with isomorphic component detection, results in optimal hypertree decompositions. We also make the procedure generic; variations of which results in two new tractable decompositions: hyperspread and connected hypertree. We show that the hyperspread width is bounded by both the hypertree width and the spread cut width, which solves a recently stated open problem. In our experiments on several realistic instances, our methods find many optimal decompositions, while the previous methods can find at most one.
@inproceedings{ijcai2007p27,
title = {Backtracking Procedures for Hypertree, HyperSpread and Connected Hypertree Decomposition of CSPs},
author = {Subbarayan, Sathiamoorthy and Andersen, Henrik Reif},
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 = {180--184},
year = {2007},
url = {https://ijcai.org/proceedings/2007/27},
}
TY - CPAPER TI - Backtracking Procedures for Hypertree, HyperSpread and Connected Hypertree Decomposition of CSPs AU - Subbarayan, Sathiamoorthy AU - Andersen, Henrik Reif T2 - Proceedings of the Twentieth International Joint Conference on Artificial Intelligence, IJCAI-07 PB - International Joint Conferences on Artificial Intelligence PY - 2007 SP - 180 EP - 184 UR - https://ijcai.org/proceedings/2007/27 ER -Copied
Machine-readable versions of this paper, for tools and AI agents:
