Title: Graph Isomorphism Using Parallel Processing Techniques
Date/Time: June 14^th, 2017 @ 3:00 PM
Place: 223 Atanasoff Hall 
Major Professor: Pavankumar Aduri
Committee Members: Carl Chang and Simanta Mitra

Abstract:

Graph isomorphism (GI) is one of the classical concepts in graph theory. The problem of GI is to find out whether the two input graphs are isomorphic or not. This problem has several applications in practice. Graph isomorphism is one of the problems which is known to be in NP. Interestingly GI is neither known to be NP-complete nor known to have a polynomial algorithm.

Several researchers have worked on creating an algorithm that can check isomorphism between graphs. One of the well-known GI algorithms is due to Brendan McKay. His algorithm popularly known as   Nauty (No AUTomorphisms, Yes?). Though the algorithm has an exponential runtime for certain inputs, it runs very fast under most 
circumstances. In this article, we introduce the essential components of the algorithm and provide a parallel implementation of the same algorithm using MapReduce paradigm.