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, May 16, 2011

Humboldt-Universität zu Berlin
Institut für Informatik
Rudower Chaussee 25
12489 Berlin
room 3.113 (1. Etage, Haus 3)

Lecture - 14:15

Martin Grohe - Humboldt-Universität zu Berlin

Excluding Topological Subgraphs

A graph H is a topological subgraph of a graph G if a subdivision of H is isomorphic to a subgraph of G. This talk will be an introduction to the structure of graphs excluding certain graphs as topological subgraphs, building on top of Robertson and Seymour's structure theory for graphs with excluded minors.
The structural insights lead, for fixed every graph H, to a cubic time algorithm that tests if a given graph G contains H as a topological subgraph. This shows that topological subgraph testing is fixed-parameter tractable, resolving a longstanding open question of Downey and Fellows from 1992. As a corollary, for every H we obtain a cubic time algorithm that tests if there is an immersion of H into a given graph G. This answers another open question raised by Downey and Fellows in 1992.
This is joint work with Ken-Ichi Kawarabayashi, Daniel Marx, and Paul Wollan.

Colloquium - 16:00

Max Klimm - TU Berlin

Optimal File Distribution in Peer-to-Peer Networks

We study the problem of distributing a file initially located at a server among a set of peers. Peers who downloaded the file can upload it to other peers. The server and the peers are connected to each other via a core network. The upload and download rates to and from the core are constrained by user and server specific upload and download capacities. Our objective is to minimize the makespan. We show that the problem becomes strongly NP-hard for equal upload and download capacities per peer that may differ among peers. For this case we devise a polynomial time 1+2sqrt(2)-approximation algorithm. (Joint work with Kai-Simon Goetzmann, Tobias Harks, and Konstantin Miller)

Letzte Aktualisierung: 05.05.2011