An approach to Graph Isomorphism using Spanning Trees generated by Breadth First Search
Alexey Ilchenko · OhioLink ETD Center (Ohio Library and Information Network) · 2014
Graph Isomorphism is a problem of determining whether or not a bijective function between two graphs exists which also preserves the adjacency relation between nodes.If graphs, regardless of how they are drawn or in what order the nodes are listed, are shown to be isomorphic, then they are essentially the same.This has direct applications in elds even outside of computer science and mathematics.This paper presents a novel way to determine whether this relationship between any given unweighted and undirected graphs exists by employing the invariant property of shortest distance which we exploit by generating a spanning tree using Breadth First Search.The Algorithm relies on guessing and backtracking, but the number of guesses which are available to be made are heavily reduced from a naive approach.The running times of the presented algorithm are measured by exploring some growth parameters of random graphs.