Name
Abstract | ||
|---|---|---|
We give an algorithm to decide isomorphism of hypergraphs of rank k in time exp (Otilde(k2radicn)), 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 Cn (Luks 1999). |
Year | DOI | Venue |
|---|---|---|
2008 | 10.1109/FOCS.2008.80 | Philadelphia, PA |
Keywords | Field | DocType |
computational complexity,graph theory,isomorphism,exponential time,graph isomorphism testing,hypergraphs,algorithm,graph isomorphism,hypergraph,moderately exponential,permutation groups | Graph theory,Discrete mathematics,Combinatorics,Vertex (geometry),Graph isomorphism,Hypergraph,Constraint graph,Rank (graph theory),Isomorphism,Mathematics,Bounded function | Conference |
ISSN | ISBN | Citations |
0272-5428 | 978-0-7695-3436-7 | 10 |
PageRank | References | Authors |
0.78 | 9 | 2 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Laszlo Babai | 1 | 3537 | 573.58 |
| Paolo Codenotti | 2 | 10 | 0.78 |