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 ddimensional WeisfeilerLehman algorithm. For fixed d, the WeisfeilerLehman algorithm runs in polynomial time, and it can distinguish many, but not all pairs of nonisomorphic graphs. I will present different polynomial time algorithms that can distinguish more pairs of graphs in polynomial time.
Files:
Speaker: Harm Derksen
Institution: U. Michigan
Event Organizer:
