Isomorphism Testing for Restricted Graph Classes, Fachbücher von Fabian Wagner

Das Buch "Isomorphism Testing for Restricted Graph Classes" von Fabian Wagner bietet eine umfassende Analyse des Graph-Isomorphismusproblems (GI), das sich mit der Frage beschäftigt, ob eine bijektive Abbildung zwischen den Knoten zweier Graphen existiert, die die Adjazenzbeziehungen bewahrt. Das Problem ist in der Komplexitätstheorie von besonderem Interesse, da es weder als NP-vollständig noch als in P klassifiziert ist. In diesem Fachbuch werden spezielle Klassen von Graphen untersucht, um die bestehenden Grenzen der Komplexität zu reduzieren. Insbesondere wird nachgewiesen, dass das Isomorphismustesten für planare Graphen sowie für K_{3,3}- und K_5-minorfreie Graphen in logarithmischem Raum möglich ist. Darüber hinaus wird ein neuer Obergrenzenansatz für Graphen mit beschränkter Baumweite präsentiert. Das Buch behandelt auch die Komplexität des Isomorphismusproblems in Bezug auf Gruppen oder Quasigruppen, die in Tabellenform dargestellt sind, und verbessert einige Obergrenzen für Erreichbarkeitsprobleme in den genannten Graphklassen.