Isomorphie und Ähnlichkeit von Graphen


Das Graphisomorphieproblem (kurz GI) ist eines der wenigen verbliebenen natürlichen Kandidaten für ein NP-Problem, das weder in P liegt, noch NP-vollständig ist. Nur für bestimmte Einschränkungen von GI gelang es bisher, effiziente Algorithmen zu finden, und einige hiervon konnten sogar als vollständig für wichtige Teilklassen von P eingeordnet werden. Wir wollen diese Vollständigkeitsresultate auf weniger restriktive Einschränkungen von GI verallgemeinern. In Anwendungen ist häufig auch von Interesse, wie sehr sich zwei gegebene Graphen unterscheiden. Hierfür wurden bisher meist Heuristiken verwendet, ohne dass diese vom theoretischen Standpunkt aus befriedigend untersucht wurden. Wir wollen bekannte Isomorphiealgorithmen erweitern, damit sie im Fall von nichtisomorphen Eingabegraphen ein Maß für deren Unterschiedlichkeit ausgeben. Außerdem wollen wir das uneingeschränkte GI weiter untersuchen und dabei insbesondere zufällige Eingabeverteilungen in Betracht ziehen, die nahe am Worst-Case liegen. Für das klassische Average-Case-Modell sind bereits Algorithmen bekannt, die GI mit hoher Wahrscheinlichkeit effizient und korrekt entscheiden.


Projektleitung
Köbler, Johannes Prof. Dr. (Details) (Algorithmen und Komplexität II)

Laufzeit
Projektstart: 12/2010
Projektende: 05/2018

Zuletzt aktualisiert 2020-01-06 um 17:42