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
partners


Monday Lecture and Colloquium


Monday, May 2, 2016

Technische Universität Berlin
Institut für Mathematik
Straße des 17. Juni 136
10623 Berlin
room MA 041



Lecture - 14:15

Mihał Pilipczuk - University of Warsaw

Bidimensionality and beyond: the story of parameterized algorithms on planar graphs


Abstract:
It was realized already in the early days of the algorithm design that many problems that are intractable in general, become efficiently solvable on planar graphs. In the paradigm of parameterized complexity, the fundamental technique for designing fast algorithms on planar graphs is bidimensionality: exploiting the linear relation between "tree-likeness" of a planar graph and the maximum size of a bidimensional object that can be embedded into it. Even though bidimensionality provides close to optimal algorithms for a number of fundamental parameterized problems on planar graphs, there are numerous cases where the technique fails to be applicable, and where we are unable to use the planarity assumption in any meaningful way. During the talk we will introduce the method of bidimensionality, discuss its strengths and weaknesses, and present the most recent advances on extending it to more general classes of problems.




Colloquium - 16:00

Sebastian Siebertz - Technische Universität Berlin


Game Characterisations of Bounded Expansion and Nowhere Dense Classes of Graphs

Abstract:
Bounded expansion and nowhere dense classes of graphs were introduced by Nesetril and Ossona de Mendez as formalisations of uniformly sparse graphs. Grohe, Kreutzer and Siebertz presented a very intuitive characterisation of nowhere dense classes in terms of a game, called the splitter game. A similar game characterisation can be given for classes of bounded expansion. In this talk, we are going to compare the two games and derive new bounds for parameters that characterise bounded expansion and nowhere dense classes of graphs. We are going to present our recent result that classes with excluded topological minors admit uniform winning strategies in the game and sketch a proof that such classes admit efficient model-checking for successor-invariant first-order formulas.



Letzte Aktualisierung: 26.04.2016