Approaches to Solving the Graph Isomorphism Problem
MetadataShow full item record
In this paper I propose a polynomial time algorithm for the Graph Isomorphism problem, which always returns a correct answer in the case that the input graphs are non-cospectral or isomorphic. Although I have no correctness proof in the general case, I suspect that most if not all inputs return a correct answer after the execution of my algorithm. This paper assumes no previous knowledge of the problem itself, however a basic understanding of Theoretical Computer Science is assumed. Explained in this paper are the techniques and approaches to breaking down this problem into something that is more manageable. Finally, I discuss problems relating to Graph Isomorphism that remain open at the time of writing this paper.