[home] - [up]


Lectures and Colloquia during the semester



Monday, May 29, 2006

Technische Universität Berlin
Straße des 17. Juni 136
10623 Berlin
Math building - Room MA 041 - map -
Lecture - 14:15

Fritz Eisenbrand - MPI Saarbrücken

The Stable Set Polytope of Quasi-Line Graphs

Abstract: It is a long standing open problem to find an explicit description of the stable set polytope of \it{claw-free graphs}. Yet more than 20 years after the discovery of a polynomial algorithm for the maximum stable set problem for claw-free graphs, there is even no conjecture at hand today. Such a conjecture exists for the class of \it{quasi-line graphs}. This class of graphs is a proper superclass of line graphs and a proper subclass of claw-free graphs for which it is known that not all facets have 0/1 normal vectors. The \it{Ben Rebea conjecture} states that the stable set polytope of a quasi-line graph is completely described by so called \it{clique-family} inequalities.

In this lecture, I will present an introduction to the subject and a proof of the Ben Rebea conjecture.

Joint work with G. Oriolo, G. Stauffer and P. Ventura


Colloquium - 16:00

Oliver Klein - FU Berlin

On Reference Points and Applications

Abstract: Comparing point sets under transformations has important applications in computer vision and shape matching. For most distance measures on point sets, exact minimization of the distance under translations, rigid motions or even similarity operations does not seem to be efficient enough for practical purposes. The usage of reference points has turned out to be good approach for the construction of approximation algorithms. In this talk we will present new results on this topic, focused both on general features and applications.


[home] - [up] - [top]