Prof. Johannes Köbler
Profilbild Köbler

Prof. Johannes Köbler

Mathematisch-Naturwissenschaftliche Fakultät
Institut für Informatik

Komplexität und Kryptographie

 
Expertise

Der Schwerpunkt unserer Forschungsinteressen liegt auf Algorithmen für und der Komplexität von algebraischen Problemen, mit einer besonderen Betonung des Graphisomorphieproblems und verwandten algorithmischen Problemen. Es ist seit langem eine offene Frage, ob das Graphisomorphieproblem für allgemeine Graphen in Polynomialzeit gelöst werden kann. Für viele eingeschränkte Graphklassen sind allerdings effiziente Algorithmen bekannt (z.B. für Graphen mit beschränkter Bauweite, beschränkten Farbklassen, für bestimmte Schnittgraphen wie z.B. Intervallgraphen sowie für alle Graphklassen, die unter Minorenbildung abgeschlossen sind). Daneben untersuchen wir verwandte Probleme wie Kanonisierung und Ähnlichkeit von Graphen sowie theoretische Fragestellungen im Umkreis der Kryptographie.

Profil-Link teilen
Der Link wurde kopiert.