direkt zum Inhalt springen

direkt zum Hauptnavigationsmenü

Sie sind hier

TU Berlin

Inhalt des Dokuments

Inhalt des Dokuments

Menschen

ERC Grant für TU-Informatiker

Donnerstag, 16. April 2015

Stephan Kreutzers Forschungen sollen zu einem grundlegenden Verständnis gerichteter Graphen führen

Mit dem ERC Grant von 1,9 Millionen Euro richtet Stephan Kreutzer eine Forschungsgruppe ein
Lupe

Prof. Dr. Stephan Kreutzer erhält für sein Forschungsprojekt „Structure Theory for Directed Graphs“ (DISTRUCT) den hoch angesehenen ERC Consolidator Grant der EU. 1,9 Millionen Euro bekommt der Informatiker in den nächsten fünf Jahren für Grundlagenforschung. Der ERC Consolidator Grant wird von der EU an exzellente innovative Nachwuchswissenschaftlerinnen und -wissenschaftler vergeben.

Durchbruch nach zwei Jahrzehnten

20 Jahre kamen die Forschungen zur Struktur gerichteter Graphen nicht voran, weil ein zentraler Baustein fehlte. Doch 2014 gelang Prof. Dr. Stephan Kreutzer und seinem japanischen Kollegen Prof. Dr. Ken-ichi Kawarabayashi vom National Institute of Informatics der Durchbruch: Die beiden Wissenschaftler konnten die Existenz gitterartiger Strukturen in gerichteten Graphen nachweisen. Damit hatten sie dieses seit zwei Jahrzehnten offene Problem gelöst.

Die bahnbrechende Arbeit ermöglichte es Stephan Kreutzer, sein Forschungsprojekt „Structure Theory for Directed Graphs“ (DISTRUCT) bei der EU zu beantragen, das nun bewilligt wurde und mit dem hoch angesehenen ERC Consolidator Grant gefördert wird. „Die 1,9 Millionen Euro sollen helfen, an der TU Berlin eine Forschergruppe zu dem Thema Strukturtheorie gerichteter Graphen aufzubauen“, sagt Kreutzer, der seit vier Jahren an der TU Berlin lehrt und zuvor mehrere Jahre in Oxford und Cambridge arbeitete.

In den kommenden fünf Jahren wollen Kreutzer und seine Kolleginnen und Kollegen beim Verständnis über die Struktur gerichteter Graphen ein ganzes Stück vorankommen. „Im Moment“, so der Informatiker, „ist das Wissen über deren Struktur sehr rudimentär. Wir verstehen nicht so recht, wie sie funktionieren, ganz im Gegensatz zu ungerichteten Graphen, die sehr gut erforscht sind.“

Ziel des Projektes ist es daher, Aussehen und grundlegende Eigenschaften gerichteter Graphen zu untersuchen und diese Erkenntnisse zur Entwicklung effizienter Algorithmen, also schneller Lösungsverfahren für viele schwierige Probleme in der Informatik, zu nutzen. Solche Probleme entstehen zum Beispiel im Zusammenhang mit Sicherheitsfragen von Softwareprogrammen oder bei der Verifikation von Steuerungen in Flugzeugen oder Kernkraftwerken. Um auszuschließen, dass die Schaltkreise, die zum Beispiel Kühlkreisläufe in Atomkraftwerken oder Teile von Flugzeugen kontrollieren, fehlerhaft sind, muss bewiesen werden, dass sie fehlerlos gebaut sind. „Das ist ein Problem gerichteter Graphen“, erklärt Prof. Dr. Stephan Kreutzer.

Graphen sind ein mathematisches Modell und bestehen aus einer Menge von Objekten (Knoten) und einer Menge von Linien (Kanten), die jeweils zwei Knoten miteinander verbinden. Die Wissenschaft unterscheidet zwischen gerichteten und ungerichteten Graphen. Das Flugnetz einer Airline, das Organigramm eines Unternehmens, Routennetze beim Gütertransport sowie jedes Computer-Netzwerk wie das Internet sind als Graphen darstellbar. Gerichtete Graphen können daher für die Lösung der verschiedensten Arten von algorithmischen Problemen, bei denen es um Fragen der Optimierung geht, angewendet werden. Zur Lösung hochkomplexer Transportprobleme oder bei Problemen der Konstruktion des Word Wide Web werden gerichtete Graphen genutzt. Aber auch bei der Analyse metabolischer Netzwerke in der Biologie kommen sie zum Einsatz.Ihre wegweisende Arbeit „The Directed Grid Theorem“ werden Ken-ichi Kawarabayashi und Stephan Kreutzer auf der renommierten internationalen Fachtagung STOC 2015, dem 47. ACM Symposium on Theory of Computing, in Portland (USA) im Juni dieses Jahres vorstellen.

http://arxiv.org/abs/1411.5681

Sybille Nitsche "TU intern" April 2015

Zusatzinformationen / Extras

Direktzugang

Schnellnavigation zur Seite über Nummerneingabe

Diese Seite verwendet Matomo für anonymisierte Webanalysen. Mehr Informationen und Opt-Out-Möglichkeiten unter Datenschutz.