Monday, June 4, 2007
Technische Universität Berlin
Fak. II, Institut für Mathematik
Str. des 17. Juni 136
10623 Berlin
room MA 041
Lecture - 14:15
Abstract:
In a series running up to currently 23 papers, Robertson and Seymour
developed their groundbreaking graph minor theory, culminating in the
proof of Wagner's conjecture that in every infinite set of finite
graphs, one is a minor of another.
Many parts of this theory have found algorithmic applications -
perhaps the notion of tree-width being the most prominent. But also
other parts of the theory are used in the design of algorithms. In
particular, strong decomposition theorems exploiting the structure of
graphs with excluded minors have been used to design explicit
algorithms for various problems on graphs excluding a fixed minor.
Logical approaches to algorithms and graph minors study ways of
describing algorithmic problems in a logical formalism. For instance,
many natural problems on graphs can be formalised in first-order logic
or extensions of it. Results in this area are of the form that every
problem that can be described in a given formalism can be evaluated
efficiently on planar graphs, graph classes of small tree width, etc.
In this way, one can easily verify that a problem is tractable
on a certain class of graphs, but simply formalising the problem in a
suitable logical formalism.
In this talk we will give an overview of known results in this area
and present some of the methods used in their proofs. We will also
present some new results. One is a generalisation of algorithmic results
on graphs excluding a fixed minor to a larger class of graphs including
bounded degree graphs. Another application of the logical approach is a
way to compute the set of excluded minors for certain classes of
graphs.
Colloquium - 16:00
Abstract:
Algorithmic matroid theory has recently attracted a substantial amount of interest of researchers. Analogues of classical algorithmic results for graphs of bounded tree-width has been established for matroids of bounded branch-width (which are representable over finite fields). In the talk, we will survey the results and methods applied in this area and compare them to the results on graphs. At the end of the talk, we will present a new matroid decomposition that allows to extend some of the previous algorithmic results on matroids representable over finite fields to the class of all matroids.