Tricky Problems for Graphs of Bounded Treewidth
In this talk I will consider computational problems that (A) can be solved in polynomial time for graphs of bounded treewidth and (B) where the order of the polynomial time bound is expected to depend on the treewidth of the instance.
Zusammenfassung
|
Was
|
Tricky Problems for Graphs of Bounded Treewidth
|
|
Wer
|
Dr. Stefan Szeider, Durham University, United Kingdom
|
|
Wo
|
TU Wien, Seminarraum 184/2, 3.Stock, blauer Bereich, Favoritenstr. 9-11
|
|
Wann
|
22/01/09
13:30 - 14:30
|
|
Link
|
http://www.dur.ac.uk/stefan.szeider
|
Details
Der Arbeitsbereich für Datenbanken und Artificial Intelligence am Institut für Informationssysteme lädt zu folgenden Vorträgen ein.
Abstract
In this talk I will consider computational problems that (A) can be solved in polynomial time for graphs of bounded treewidth and (B) where the order of the polynomial time bound is expected to depend on the treewidth of the instance. Among the considered problems are coloring problems, factor problems, orientation problems and satisfiability problems. I will present an algorithmic meta-theorem (an extension of Courcelle's Theorem) that provides a convenient way for establishing (A) for some of the considered problems and I will explain how concepts from parameterized complexity theory can be used to establish (B).
