Logik in der Informatik
Prof. Dr. Martin Grohe

Institut für Informatik

Mitarbeiterseminar Logik in der Informatik

Freitag, 4. November 2005, 11:15 Uhr
RUD 25, Raum 4.410

Decomposition Methods without Decompositions in Constraint Satisfaction

Hubie Chen
Humboldt-Universität zu Berlin

The Constraint Satisfaction Problem (CSP) is a general framework for the modelling of search problems. Due to its general intractability, there has been much research aimed at identifying restrictions of the CSP that guarantee polynomial-time tractability. One line of work -- the topic of this talk -- has focused on so-called structural restrictions, or "decomposition methods", where the interaction among variables is restricted. This line of work has its origins in work of Dechter and Pearl ('89) and Freuder ('90) on bounded treewidth. In this talk, I will survey some of the results in the area, with a focus towards recent work (joint with Victor Dalmau) showing the tractability of generalized hypertreewidth in CSP (paper available on my home page). A feature of this recent work is that the algorithms given do not need or compute any form of tree decomposition, even though the notion of generalized hypertreewidth is defined in terms of tree decompositions.

Zurück zur Vortragsübersicht 

Last modified: Tue Nov 15 11:36:44 CET 2005
André Hernich