The INI has a new website!

This is a legacy webpage. Please visit the new site to ensure you are seeing up to date information.

Skip to content



Beyond Hypertee Width: Decomposition methods without decompositions

Dalmau, V (Pompeu Fabra)
Thursday 23 February 2006, 11:00-12:00

Seminar Room 1, Newton Institute


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.


MP3MP3 Real AudioReal Audio

Back to top ∧