Prof. Johannes Köbler
Komplexität und Kryptographie
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.