Name
Abstract | ||
|---|---|---|
In recent results the complexity of isomorphism testing on graphs of bounded treewidth is improved to TC1 [17] and further to LogCFL [11]. The computation of canonical forms or a canonical labeling provides more information than isomorphism testing. Whether canonization is in NC or even TC1 was stated as an open question in [18]. Köbler and Verbitsky [20] give a TC2 canonical labeling algorithm. We show that a canonical labeling can be computed in AC1. This is based on several ideas, e.g. that approximate tree decompositions of logarithmic depth can be obtained in logspace [15], and techniques of Lindells tree canonization algorithm [22]. We define recursively what we call a minimal description which gives with respect to some parameters in a logarithmic number of levels a canonical invariant together with an arrangement of all vertices. From this we compute a canonical labeling. |
Year | Venue | Keywords |
|---|---|---|
2011 | Electronic Colloquium on Computational Complexity (ECCC) | bounded treewidth,isomorphism testing,canonical invariant,logarithmic depth,approximate tree decomposition,lindells tree canonization algorithm,tc2 canonical,minimal description,logarithmic number,canonical form |
DocType | Volume | Citations |
Journal | 18 | 2 |
PageRank | References | Authors |
0.36 | 17 | 1 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Fabian Wagner | 1 | 20 | 3.87 |