You are here

Efficient Isomorphism Detection in Searches


Speaker Info:

John Bate
Department of Computer Science
University of British Columbia


Searching efficiently for combinatorial objects requires the elimination of isomorphic configurations, either during the search process itself, or from the results generated. Graph isomorphism methods are used to do this, and there is little room for improvement in the existing algorithms, when applied to individual graphs. However, a method will be presented which can significantly improve their efficiency when applied to large sets of graphs.

I will give a general introduction to the graph isomorphism problem, and a broad outline of the methods used by traditional algorithms in this area, followed by the enhancement for processing large sets of graphs.