A Polynomial Time Algorithm for Graph Isomorphism

2007/11/13 by Reiner Czerwinski, Czerwinski, Reiner
Computer Science · #Algorithms and Data Compression #Advanced Graph Theory Research #Graph Theory and Algorithms

paper · pdf · doi:10.48550/arxiv.0711.2010

Abstract

We claimed that there is a polynomial algorithm to test if two graphs are isomorphic. But the algorithm is wrong. It only tests if the adjacency matrices of two graphs have the same eigenvalues. There is a counterexample of two non-isomorphic graphs with the same eigenvalues.

Related

• Isomorphism of graphs-a polynomial test
• Polynomial Time Algorithm for Graph Isomorphism Testing
• The polynomial algorithm for graphs' isomorphism testing
• The direct algorithm for solving of the graph isomorphism problem
• Testing Isomorphism of Graphs in Polynomial Time