Beyond Hypertree Width: Decomposition Methods Without Decompositions
<|reference_start|>Beyond Hypertree Width: Decomposition Methods Without Decompositions: 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.<|reference_end|>
@article{chen2005beyond,
    title={Beyond Hypertree Width: Decomposition Methods Without Decompositions},
    author={Hubie Chen and Victor Dalmau},
    journal={arXiv preprint arXiv:cs/0505035},
    year={2005},
    archivePrefix={arXiv},
    eprint={cs/0505035},
    primaryClass={cs.CC cs.AI}
}