Büro: O 27 / 532
Telefon: 0731/50-24223
Telefax: 0731/50-24102
Meine Email-Adresse: <Vorname>.<Nachname> (at) uni-ulm.de
In meinem Forschungsgebiet im Institut Theoretische Informatik befasse
ich mich mit komplexitätstheoretischen Betrachtungen zum Problem
Graphenisomorphie
sowie Graphenisomorphie auf spezielle Graphklassen.
Das Graphenisomorphieproblem (GI) ist ein grundlegendes Problem
in der Graphentheorie und ist intensiv untersucht worden.
Zwei Graphen sind genau dann isomorph, wenn zwischen den beiden Graphen
eine bijektive Abbildung der Knoten aufeinander
existiert, bei der die Adjazenzbeziehungen zwischen den Knoten erhalten
bleiben müssen.
Das Forschungsgebiet umfasst folgende Fragestellungen:
a) die Suche nach besseren unteren Schranken in Bezug auf
Komplexitätsklassen
Dabei ist noch offen, ob es Algorithmen mit polynomieller Laufzeit
gibt, (man spricht in diesem Zusammenhang auch von
effizienten Algorithmen) bzw. ob für GI sogar durch
Parallelisierung Algorithmen mit polylogarithmischer Laufzeit
existieren.
b) die Suche nach neuen unteren und oberen Schranken für das Isomorphieproblem auf bestimmten Graphklassen
Man untersucht, wie schwierig das Isomorphieproblem
ist, wenn man die Graphen in der Eingabe auf eine bestimmte Graphklasse beschränkt.
Beispiele für Graphklassen: Bäume, planare Graphen, Graphen mit beschränktem Knotengrad,
oder Turniergraphen.
Publikationen: