Donnerstag, 12. November 2015
Effektiver Algorithmus zur Prüfung von Graphen-Isomorphie entwickelt?
klauslange,16:53h
Wurde ein Algorithmus entwickelt, der die Isomorphie zweier Graphen korrekt überprüfen kann?
Zur Prüfung der Isomorphie zweier gegebener Graphen ist bislang kein effizienter Algorithmus bekannt. Mehr noch, die Komplexität des bestmöglichen Algorithmus ist bis heute noch nicht bestimmt. Insbesondere ist die Isomorphie von Graphen eines der wenigen bekannten Probleme in NP, für die weder bekannt ist, ob sie in P enthalten, noch ob sie NP-vollständig sind.
Doch nun wurde eine Lösung vorgestellt.
Siehe hier.
Zur Prüfung der Isomorphie zweier gegebener Graphen ist bislang kein effizienter Algorithmus bekannt. Mehr noch, die Komplexität des bestmöglichen Algorithmus ist bis heute noch nicht bestimmt. Insbesondere ist die Isomorphie von Graphen eines der wenigen bekannten Probleme in NP, für die weder bekannt ist, ob sie in P enthalten, noch ob sie NP-vollständig sind.
Doch nun wurde eine Lösung vorgestellt.
Siehe hier.
... comment
