Abstract | ||
---|---|---|
We give a polynomial-time oracle algorithm for Tournament Canonization that accesses oracles for Tournament Isomorphism and Rigid-Tournament Canonization. Extending the Babai-Luks Tournament Canonization algorithm (Babai and Luks (1983) [4]), we give an n^O^(^k^^^2^+^l^o^g^n^) algorithm for canonization and isomorphism testing of k-hypertournaments, where n is the number of vertices and k is the size of hyperedges. |
Year | DOI | Venue |
---|---|---|
2010 | 10.1016/j.jcss.2009.09.001 | J. Comput. Syst. Sci. |
Keywords | Field | DocType |
polynomial time,babai-luks tournament canonization algorithm,permutation groups,isomorphism testing,polynomial-time oracle algorithm,tournaments,tournament canonization,graph isomorphism,turing reductions,accesses oracle,rigid-tournament canonization,tournament isomorphism,permutation group | Graph canonization,Discrete mathematics,Tournament,Combinatorics,Vertex (geometry),Graph isomorphism,Permutation group,Isomorphism,Time complexity,Mathematics,Graph isomorphism problem | Journal |
Volume | Issue | ISSN |
76 | 7 | Journal of Computer and System Sciences |
ISBN | Citations | PageRank |
3-540-49694-7 | 4 | 0.48 |
References | Authors | |
8 | 3 |
Name | Order | Citations | PageRank |
---|---|---|---|
V. Arvind | 1 | 122 | 12.03 |
Bireswar Das | 2 | 66 | 10.61 |
Partha Mukhopadhyay | 3 | 91 | 12.71 |