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