Friday, May 23, 2008 — 3:30 PM to 4:30 PM EDT

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

Location 
MC - Mathematics & Computer Building
5158
200 University Avenue West

Waterloo, ON N2L 3G1
Canada

S M T W T F S
26
27
28
29
30
31
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
1
2
3
4
5
  1. 2022 (12)
    1. January (12)
  2. 2021 (103)
    1. December (3)
    2. November (7)
    3. October (6)
    4. September (12)
    5. August (6)
    6. July (10)
    7. June (12)
    8. May (7)
    9. April (9)
    10. March (13)
    11. February (8)
    12. January (10)
  3. 2020 (119)
  4. 2019 (167)
  5. 2018 (136)
  6. 2017 (103)
  7. 2016 (137)
  8. 2015 (136)
  9. 2014 (88)
  10. 2013 (48)
  11. 2012 (39)
  12. 2011 (36)
  13. 2010 (40)
  14. 2009 (40)
  15. 2008 (39)
  16. 2007 (15)