A Polynomial Time Algorithm for Graph Isomorphism

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

paper · pdf · doi:10.48550/arxiv.0711.2010

arxiv created 2022/10/15 · arxiv updated 2022/10/18

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.

Cited by

• Polynomial Time Algorithm for Graph Isomorphism Testing

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