Name
Abstract | ||
|---|---|---|
We study the problem of canonizing hypergraphs under Abelian group action and show tight complexity bounds. Our approach is algebraic. We transform the problem of graph canonization to the problem of canonizing associated algebraic structures for which we develop a parallel algorithm. Specifically, we show that the problem of computing canonical labelings for hypergraphs of color class size 2 is computable in FL⊕L. For general hypergraphs, under Abelian permutation group action, for the canonization problem we show an upper bound of randomized FLGapL (which is contained in randomized NC2). This is a nearly tight characterization since the problem is hard for the complexity class FLGapL. The problem is also in deterministic NC3. |
Year | DOI | Venue |
|---|---|---|
2011 | 10.1007/978-3-642-22685-4_39 | COCOON |
Keywords | Field | DocType |
abelian permutation group action,graph canonization,abelian group action,canonizing hypergraphs,complexity class flgapl,algebraic structure,randomized flgapl,color class size,general hypergraphs,canonization problem | Graph canonization,Complexity class,Discrete mathematics,Abelian group,Combinatorics,Algebraic number,Upper and lower bounds,Algebraic structure,Constraint graph,Permutation group,Mathematics | Conference |
Citations | PageRank | References |
1 | 0.36 | 18 |
Authors | ||
2 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| V. Arvind | 1 | 52 | 4.34 |
| Johannes Köbler | 2 | 580 | 46.51 |