idw – Informationsdienst Wissenschaft
Nachrichten, Termine, Experten
Nachrichten, Termine, Experten
Forschungen sollen zu einem grundlegenden Verständnis gerichteter Graphen führen
20 Jahre kamen die Forschungen zur Struktur gerichteter Graphen nicht voran, weil ein zentraler Baustein fehlte. Doch 2014 gelang Dr. Stephan Kreutzer, Professor an der TU Berlin, und seinem japanischen Kollegen Prof. Dr. Ken-ichi Kawarabayashi vom National Institute of Informatics in Tokio 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 Prof. Dr. Stephan Kreutzer, sein Forschungsprojekt „Structure Theory for Directed Graphs“ (DISTRUCT) bei der EU zu beantragen, das nun bewilligt wurde und wofür er den hoch angesehenen ERC Consolidator Grant bekommt. 1,9 Millionen Euro stehen ihm für seine Grundlagenforschung in den nächsten fünf Jahren zur Verfügung. Der ERC Consolidator Grant wird von der EU an exzellente Nachwuchswissenschaftlerinnen und -wissenschaftler vergeben und fördert deren innovative vielversprechende Forschung. „Das Geld soll 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, müssen sie verifiziert werden. Das heißt, es muss bewiesen werden, dass sie fehlerlos gebaut sind. „Und das ist letztendlich ein Problem gerichteter Graphen“, erklärt Prof. Dr. Stephan Kreutzer.
Graphen sind ein mathematisches Modell und bestehen aus einer Menge von Objekten (auch Knoten genannt) und einer Menge von Linien (auch Kanten genannt), die jeweils zwei Knoten miteinander verbinden, sie also in Relation zueinander setzen. 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 – sie 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 World 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 übrigens 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
Fotomaterial zum Download:
www.tu-berlin.de/?=159237
Weitere Informationen erteilt Ihnen gern:
Prof. Dr. Stephan Kreutzer
TU Berlin
Fachgebiet Logik und Semantik
Tel.: 030/314-29088
E-Mail: stephan.kreutzer@tu-berlin.de
Merkmale dieser Pressemitteilung:
Journalisten, Wissenschaftler
Informationstechnik, Mathematik
überregional
Forschungsergebnisse, Personalia
Deutsch
Sie können Suchbegriffe mit und, oder und / oder nicht verknüpfen, z. B. Philo nicht logie.
Verknüpfungen können Sie mit Klammern voneinander trennen, z. B. (Philo nicht logie) oder (Psycho und logie).
Zusammenhängende Worte werden als Wortgruppe gesucht, wenn Sie sie in Anführungsstriche setzen, z. B. „Bundesrepublik Deutschland“.
Die Erweiterte Suche können Sie auch nutzen, ohne Suchbegriffe einzugeben. Sie orientiert sich dann an den Kriterien, die Sie ausgewählt haben (z. B. nach dem Land oder dem Sachgebiet).
Haben Sie in einer Kategorie kein Kriterium ausgewählt, wird die gesamte Kategorie durchsucht (z.B. alle Sachgebiete oder alle Länder).
