Graduiertenkolleg: Methods for Discrete Structures

Deutsche Forschungsgemeinschaft
faculty | junior-faculty | postdocs | students | associate students | former students | former associate students
locations | Term schedule | history
predoc-courses | schools | block-courses | workshops

Monday Lecture and Colloquium

Monday, October 31, 2011

Technische Universität Berlin
Institut für Mathematik
Straße des 17. Juni 136, 10623 Berlin
room MA 041

Lecture - 14:15

Stephan Kreutzer - TU Berlin

Tractability through Graph and Digraph Minors

Many natural computational problems on graphs, such as finding dominating or independent sets of a certain size, are well known to be intractable, both in the classical sense as well as in the framework of parameterized complexity. Much work therefore has focussed on exhibiting specific classes of graphs on which these problems become tractable.
One aspect of this research is to identify classes of graphs which are
1) as general as possible so that graphs of this form can be used in a wide range of applications but
2) restricted enough so that typical algorithmic problems become tractable.

For this, methods derived from the structure theory for undirected graphs has proved to be very successful. For instance, it has been shown that a many hard problems are tractable on graph classes of bounded tree-width or which exclude a fixed minor.
Towards a Structure Theory for Directed Graphs based on Minors While in the case of undirected graphs, there is a rich structure theory which can be used to establish tractability results for these problems on large classes of undirected graphs, such a theory is much less developed for directed graphs. However, as directed graphs occur naturally in many applications in computer science, developing such a structure theory for directed graphs seems to be an important goal.
In this talk we will review some of the structural methods used to solve hard computational methods on specific classes of undirected graphs, in particular methods based on excluding minors or new approaches based on nowhere denseness.
In the second part of the talk, we will focus on very recent ideas to generalise the minor theory to directed graphs for obtaining tractability results on large classes of digraphs.

Instead of Colloquium - 16:00

Prof. Anja Feldmann Ph.D. - TU Berlin und Telekom Innovation Labatories

Leibniz-Vorlesung 2011:
Das Internet - Chancen und Herausforderungen

Letzte Aktualisierung: 26.10.2011