Beyond Hypertree Width: Decomposition Methods Without Decompositions

Simple item page
dc.creatorChen, Hubie
dc.creatorDalmau, Victor
dc.date2005-05-12
dc.date.accessioned2026-07-07T03:22:59Z
dc.date.available2026-07-07T03:22:59Z
dc.descriptionThe 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.
dc.identifierhttps://arxiv.org/abs/cs/0505035
dc.identifierhttp://arxiv.org/abs/cs/0505035
dc.identifier.urihttp://salesiana.dossiersoluciones.com/handle/123456789/32768
dc.subjectComputational Complexity
dc.subjectArtificial Intelligence
dc.titleBeyond Hypertree Width: Decomposition Methods Without Decompositions
dc.typetext

Files

Collections

arXiv