Isomorphism of hypergraphs of low rank in moderately exponential time

被引：25

作者：

Babai, Laszlo ^{[1
]}

Codenotti, Paolo ^{[1
]}

机构：

[1] Univ Chicago, Chicago, IL 60637 USA

来源：

PROCEEDINGS OF THE 49TH ANNUAL IEEE SYMPOSIUM ON FOUNDATIONS OF COMPUTER SCIENCE | 2008年

关键词：

D O I：

10.1109/FOCS.2008.80

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

We give an algorithm to decide isomorphism of hypergraphs of rank k in time exp ((O) over tilde (k(2)root n)), where n is the number of vertices. (The rank is the maximum size of edges; the tilde refers to a polylogarithmic factor) The case of bounded k answers a 24-year-old question and removes an obstacle to improving the worst case-bound for Graph Isomorphism testing. The best previously known bound, even for k = 3, was C-n (Luks 1999).

引用

页码：667 / 676

页数：10

共 23 条

[1]

[Anonymous], P 15 ANN ACM S THEOR

[2]

Babai L., 1992, Proceedings of the Twenty-Fourth Annual ACM Symposium on the Theory of Computing, P438, DOI 10.1145/129712.129754

[3] ON THE ORDER OF UNIPRIMITIVE PERMUTATION-GROUPS [J].