Approaches to Solving the Graph Isomorphism Problem

Show full item record

Please use this identifier to cite or link to this item: http://hdl.handle.net/1853/6494

Title: Approaches to Solving the Graph Isomorphism Problem
Author: Eikenberry, Jordy
Abstract: 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.
Type: Technical Report
URI: http://hdl.handle.net/1853/6494
Date: 2004
Relation: CC Technical Report; GIT-CC-04-09
Publisher: Georgia Institute of Technology
Subject: Graph Isomorphism
Polynomial time algorithms

All materials in SMARTech are protected under U.S. Copyright Law and all rights are reserved, unless otherwise specifically indicated on or in the materials.

Files in this item

Files Size Format View
GIT-CC-04-09.pdf 219.0Kb PDF View/ Open

This item appears in the following Collection(s)

Show full item record