Seminar Event Detail


Combinatorics

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.

Files:


Speaker:  Harm Derksen
Institution:  U. Michigan

Event Organizer:     

 

Edit this event (login required).
Add new event (login required).
For access requests and instructions, contact math-webmaster@umich.edu

Back to previous page
Back to UM Math seminars/events page.