Tutte seminar - V. Arvind

Friday, May 23, 2008 3:30 pm - 4:30 pm EDT (GMT -04:00)

Isomorphism and Canonical Labeling of Tournaments

Speaker: V. Arvind
Affiliation: Institute of Mathematical Sciences, Chennai
Room: Mathematics & Computer Building (MC) 5158

Abstract:

We give a polynomial-time oracle algorithm for canonical labeling of tournaments that accesses oracles for tournament isomorphism and for canonizing rigid tournaments. For general graphs such a result is not known. 
We'll also describe an n^{O(k^2+log n)} canonical labeling algorithm for hypertournaments with n vertices and hyperedges of size k.

(This is joint work with Bireswar Das and Partha Mukhopadhyay).