Tutte seminar - V. Arvind

Isomorphism and Canonical Labeling of Tournaments

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).