A Comparison of Structural CSP Decomposition Methods
Proceedings of the Sixteenth International Joint Conference on Artificial Intelligence. Constraint Satisfaction. Pages 394-398.
Abstract
We compare tractab le classes of constraint satisfaction problems (CSPs) . We first give a uniform prese ntation of the major structural CSP decomposition m et hods. We then introduce a new class of tractable CSPs based on the concept of hypertree decomposition recently developed in Database Theory. We introduce a framework for comparing parametric decomposition-based m et hods according to tractability criteria and compare the most relevant methods. We show that the method of hypertree decomposition dominates the others in the case of general (nonbinary) CSPs.
@inproceedings{ijcai1999p57,
title = {A Comparison of Structural CSP Decomposition Methods},
author = {Gottlob, Georg and Leone, Nicola and Scarcello, Francesco},
booktitle = {Proceedings of the Sixteenth International Joint Conference on
Artificial Intelligence, {IJCAI-99}},
publisher = {International Joint Conferences on Artificial Intelligence},
editor = {Thomas Dean},
pages = {394--398},
year = {1999},
note = {Constraint Satisfaction},
url = {https://ijcai.org/proceedings/1999/57},
}
TY - CPAPER TI - A Comparison of Structural CSP Decomposition Methods AU - Gottlob, Georg AU - Leone, Nicola AU - Scarcello, Francesco T2 - Proceedings of the Sixteenth International Joint Conference on Artificial Intelligence, IJCAI-99 PB - International Joint Conferences on Artificial Intelligence PY - 1999 SP - 394 EP - 398 UR - https://ijcai.org/proceedings/1999/57 ER -Copied
Machine-readable versions of this paper, for tools and AI agents:
