Beyond Hypertree Width: Decomposition Methods Without Decompositions Export

@incollection{citeulike:2295327, abstract = {The general intractability of the constraint satisfaction problem has motivated the study of restrictions on this problem that permit polynomial-time solvability. One major line of work has focused on structural restrictions, which arise from restricting the interaction among constraint scopes. In this paper, we engage in a mathematical investigation of generalized hypertree width, a structural measure that has up to recently eluded study. We obtain a number of computational results, including a simple proof of the tractability of CSP instances having bounded generalized hypertree width.}, author = {Chen, Hubie and Dalmau, V\'{\i}ctor}, citeulike-article-id = {2295327}, citeulike-linkout-0 = {http://dx.doi.org/10.1007/11564751_15}, doi = {10.1007/11564751_15}, journal = {Principles and Practice of Constraint Programming - CP 2005}, keywords = {decompositions}, pages = {167--181}, posted-at = {2009-05-28 17:08:51}, priority = {2}, title = {Beyond Hypertree Width: Decomposition Methods Without Decompositions}, url = {http://dx.doi.org/10.1007/11564751_15}, year = {2005} }

TY - CHAP ID - citeulike:2295327 L3 - citeulike-article-id:2295327 N2 - The general intractability of the constraint satisfaction problem has motivated the study of restrictions on this problem that permit polynomial-time solvability. One major line of work has focused on structural restrictions, which arise from restricting the interaction among constraint scopes. In this paper, we engage in a mathematical investigation of generalized hypertree width, a structural measure that has up to recently eluded study. We obtain a number of computational results, including a simple proof of the tractability of CSP instances having bounded generalized hypertree width. JF - Principles and Practice of Constraint Programming - CP 2005 EP - 181 TI - Beyond Hypertree Width: Decomposition Methods Without Decompositions SP - 167 KW - decompositions AU - Chen, Hubie AU - Dalmau, Víctor PY - 2005/// UR - http://dx.doi.org/10.1007/11564751_15 ER -