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, January 3, 2011

Humboldt-Universität zu Berlin
Institut für Informatik
Rudower Chaussee 25
12489 Berlin

Lecture - 14:15

Jiri Sgall - Charles University Prague

Frequency Allocation in Bipartite Graphs

The frequency allocation problem is motivated by a study of wireless networks. A wireless network is modeled by an undirected graph, with vertices corresponding to cells and edges representing conflicts between the cells. In each vertex we have a certain number of requests, each active for some time period. Each of the requests must be assigned a frequency so that no two requests in the same or adjacent vertices can share a frequency if they overlap in time. The objective is to minimize the total number of used frequencies. In this talk we present some of the results focusing on the case of line and bipartite graphs. Even in these simple cases the problem is surprisingly difficult and leads to interesting combinatorial questions. (Joint work with Marek Chrobak and Lukasz Jez.)

Colloquium - 16:00

Wolfgang Mulzer - FU Berlin

Triangulating the Square and Squaring the Triangle

We show that Delaunay triangulations and compressed quadtrees are equivalent structures. More precisely, we give two algorithms: the first computes a compressed quadtree for a planar point set, given the Delaunay triangulation; the second finds the Delaunay triangulation, given a compressed quadtree. Both algorithms run in deterministic linear time on a pointer machine. Our work builds on and extends previous results by Krznaric-Levcopolous Buchin-Mulzer.
As a corollary, we obtain deterministic versions of many previous algorithms related to Delaunay triangulations, such as splitting planar Delaunay triangulations, preprocessing imprecise points for faster Delaunay computation, and transdichotomous Delaunay triangulations.

Letzte Aktualisierung: 14.12.2010