skip to content

Beyond Hypertee Width: Decomposition methods without decompositions

Thursday 23rd February 2006 - 11:00 to 12:00
INI Seminar Room 1

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 talk we consider generalized hypertree width, a structural measure that has up to recently eluded study. We give a simple proof of the tractability of instances having bounded generalized hypertree width.

Presentation Material: 
University of Cambridge Research Councils UK
    Clay Mathematics Institute London Mathematical Society NM Rothschild and Sons