Friday, May 23, 2008
3:30 pm, MC 5158

V. Arvind
Institute of Mathematical Sciences, Chennai

Isomorphism and Canonical Labeling of Tournaments

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)