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, November 23, 2009

Freie Universität Berlin
Institut für Informatik
Takustrasse 9
14195 Berlin

Lecture - 14:15

Tibor Szabó - FU Berlin

On minimal Ramsey graphs

A graph G is called H-Ramsey if any two-coloring of the edges of G contains a monochromatic copy of H. An H-Ramsey graph is called H-minimal if no proper subgraph of it is H-Ramsey. Minimal Ramsey graphs were the subject of intensive research in the past four decades, going back to an innocent looking question of Erdos and Hajnal from the 60's concerning the existence of K_6-free K_3-Ramsey graphs. After an overview of the topic we concentrate on the minimum degree of H-minimal graphs, a problem initiated by Burr, Erdos, and Lovasz. We determine the smallest possible minimum degree of H-minimal graphs for numerous bipartite graphs H, including bi-regular bipartite graphs and forests. We also make initial progress for graphs of larger chromatic number. This represents joint work with Philipp Zumstein and Stefanie Zurcher.

Colloquium - 16:00

Lena Schlipf - FU Berlin

Computing the discrete Frechet distance with imprecise input

The Frechet distance is a measure of similarity between curves. The discrete Frechet distance is a variant of the Frechet distance in which we only consider vertices of polygonal curves. Most of previous works on the Frechet distance assume that the input curves are given precisely. The input curve, however, could be only an approximation; In many cases, geometric data comes from measurements of continuous real-world phenomenons, and the measuring devices have finite precision. Imprecise data can be modelled in different ways. In this talk, we assume that an imprecise point is given by a region and this point can lie anywhere in this region. We show how to compute the discrete Frechet distance between two polygonal curves when their vertices are imprecise.

Letzte Aktualisierung: 13.11.2009