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
Abstract:
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
Abstract:
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)