Humboldt-Universität zu Berlin - Mathematisch-Naturwissenschaftliche Fakultät - Institut für Informatik

Liebe KollegInnen,

am kommenden Mittwoch dem 20.7. um 10:00 wird Herr Florian Nelles einen Probevortrag zu seinem Disserationsthema halten. Der Vortrag findet auf Englisch statt und hat folgendes Thema:

Titel:
Efficient parameterized algorithms on structured graphs

Abstract:
In the first part of the thesis, we study the influence of well-known graph parameters like clique-width, modular-width, or tree-depth, on the time complexity of tractable graph problems. We give efficient parameterized algorithms for fundamental problems such as (vertex-weighted) all-pairs shortest paths, maximum matching, and triangle counting.

In the second part we explore how to combine such homogeneous structure considered in the first part of the thesis to more general and heterogeneous structure. Using algebraic expressions, we define new classes of graphs with heterogeneous structure and we present a framework for designing algorithms on such graph classes, getting running times that match the homogeneous cases.

Der Vortrag findet über Zoom statt. Die Zugangsdaten teile ich auf Anfrage sehr gern mit. Alle Interessierten sind herzlich willkommen!

Beste Grüße,
Stefan Kratsch