|Date: Friday, November 30, 2012
Location: 3866 East Hall (4:10 PM to 5:00 PM)
Title: The Graph Isomorphism Problem
Abstract: It is unknown whether two graphs can be tested for isomorphism in polynomial time. A classical approach to the Graph Isomorphism Problem is the d-dimensional Weisfeiler-Lehman algorithm. For fixed d, the Weisfeiler-Lehman algorithm runs in polynomial time, and it can distinguish many, but not all pairs of non-isomorphic graphs. I will present different polynomial time algorithms that can distinguish more pairs of graphs in polynomial time.
Speaker: Harm Derksen
Institution: U. Michigan