Monday, November 23, 2009
Freie Universität Berlin
Institut für Informatik
Takustrasse 9
14195 Berlin
Lecture - 14:15
Abstract:
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
Abstract:
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.