Tricky Problems for Graphs of Bounded Treewidth

  • 2009-01-22
  • Research

This talk will consider problems that (A) can be solved in polynomial time and (B) where the order of the polynomial time is expected to depend on the treewidth

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).

Note: This is one of the thousands of items we imported from the old website. We’re in the process of reviewing each and every one, but if you notice something strange about this particular one, please let us know. — Thanks!