2005/05/12 by Hubie Chen, Chen, Hubie, Víctor Dalmau +2 · 3 citations
Computer Science · #Advanced Graph Theory Research #Complexity and Algorithms in Graphs #Constraint Satisfaction and Optimization #cs.AI #cs.CC
paper · pdf · doi:10.48550/arxiv.cs/0505035
arxiv created 2005/05/12 · arxiv updated 2009/12/01
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.