Isomorphism and canonization of tournaments and hypertournaments

详细信息    查看全文

• 作者：V. Arvind ; Bireswar Das ; Partha Mukhopadhyay
• 关键词：Graph Isomorphism ; Tournaments ; Permutation groups ; Polynomial time ; Turing reductions
• 刊名：Journal of Computer and System Sciences
• 出版年：2010
• 出版时间：November 2010
• 年：2010
• 卷：76
• 期：7
• 页码：509-523
• 全文大小：311 K

文摘

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(k2+logn) algorithm for canonization and isomorphism testing of k-hypertournaments, where n is the number of vertices and k is the size of hyperedges.