Monday, May 16, 2011
Humboldt-Universität zu Berlin
Institut für Informatik
Rudower Chaussee 25
room 3.113 (1. Etage, Haus 3)
Lecture - 14:15
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
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)