A comparison of structural CSP decomposition methods Export

@article{GotLeoSca2000, abstract = {We compare tractable classes of constraint satisfaction problems (CSPs). We first give a uniform presentation of the major structural CSP decomposition methods. We then introduce a new class of tractable CSPs based on the concept of hypertree decomposition recently developed in Database Theory, and analyze the cost of solving CSPs having bounded hypertree-width. We provide a framework for comparing parametric decomposition-based methods 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 CSPs (i.e., CSPs of unbounded arity). We also make comparisons for the restricted case of binary CSPs. Finally, we consider the application of decomposition methods to the dual graph of a hypergraph. In fact, this technique is often used to exploit binary decomposition methods for nonbinary CSPs. However, even in this case, the hypertree-decomposition method turns out to be the most general method.}, author = {Gottlob, Georg and Leone, Nicola and Scarcello, Francesco}, citeulike-article-id = {2639516}, citeulike-linkout-0 = {http://dx.doi.org/10.1016/S0004-3702(00)00078-3}, citeulike-linkout-1 = {http://www.sciencedirect.com/science/article/B6TYF-41SCFR2-2/2/471257b683d5c8858c2e481678079def}, doi = {10.1016/S0004-3702(00)00078-3}, journal = {Artificial Intelligence}, keywords = {caesar\_paper, confirmation, hypertree\_decomposition, pods10}, month = {December}, number = {2}, pages = {243--282}, posted-at = {2008-04-07 23:57:53}, priority = {5}, title = {A comparison of structural CSP decomposition methods}, url = {http://dx.doi.org/10.1016/S0004-3702(00)00078-3}, volume = {124}, year = {2000} }

TY - JOUR ID - GotLeoSca2000 L3 - citeulike-article-id:2639516 N2 - We compare tractable classes of constraint satisfaction problems (CSPs). We first give a uniform presentation of the major structural CSP decomposition methods. We then introduce a new class of tractable CSPs based on the concept of hypertree decomposition recently developed in Database Theory, and analyze the cost of solving CSPs having bounded hypertree-width. We provide a framework for comparing parametric decomposition-based methods 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 CSPs (i.e., CSPs of unbounded arity). We also make comparisons for the restricted case of binary CSPs. Finally, we consider the application of decomposition methods to the dual graph of a hypergraph. In fact, this technique is often used to exploit binary decomposition methods for nonbinary CSPs. However, even in this case, the hypertree-decomposition method turns out to be the most general method. IS - 2 JF - Artificial Intelligence EP - 282 TI - A comparison of structural CSP decomposition methods VL - 124 SP - 243 KW - caesar_paper KW - confirmation KW - hypertree_decomposition KW - pods10 AU - Gottlob, Georg AU - Leone, Nicola AU - Scarcello, Francesco PY - 2000/12// UR - http://dx.doi.org/10.1016/S0004-3702(00)00078-3 ER -