Friday, May 16, 2014 (1:00 p.m. in Yost 306)

Title: An Approach to Graph Isomorphism Using Spanning Trees Generated by Breadth First Search

Speaker: Alexey Ilchenko (Case Western Reserve University)

Abstract: 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 fields 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 heavily 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. This Algorithm is presented as an algorithmic alternative to
previously known group theoretic approaches at solving the same problem. This paper may
be found at http://filer.case.edu/axi48/thesis/ while the supplementary code may be found at
https://github.com/ijkilchenko/GraphIsomorphism.