Name
Abstract | ||
|---|---|---|
We show that, for k constant, k-tree isomorphism can be decided in logarithmic space by giving an O(klogn) space canonical labeling algorithm. The algorithm computes a unique tree decomposition, uses colors to fully encode the structure of the original graph in the decomposition tree and invokes Lindell@?s tree canonization algorithm. As a consequence, the isomorphism, the automorphism, as well as the canonization problem for k-trees are all complete for deterministic logspace. Completeness for logspace holds even for simple structural properties of k-trees. We also show that a variant of our canonical labeling algorithm runs in time O((k+1)!n), where n is the number of vertices, yielding the fastest known FPT algorithm for k-tree isomorphism. |
Year | DOI | Venue |
|---|---|---|
2012 | 10.1016/j.ic.2012.04.002 | Inf. Comput. |
Keywords | Field | DocType |
logarithmic space,space canonical,fpt algorithm,deterministic logspace,time o,isomorphism problem,tree canonization algorithm,canonization problem,unique tree decomposition,decomposition tree,k-tree isomorphism,graph isomorphism,space complexity,graph canonization | Graph canonization,Discrete mathematics,Graph,Combinatorics,Vertex (geometry),Graph isomorphism,Automorphism,Tree decomposition,Isomorphism,Completeness (statistics),Mathematics | Journal |
Volume | ISSN | Citations |
217, | 0890-5401 | 5 |
PageRank | References | Authors |
0.42 | 30 | 4 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| V. Arvind | 1 | 52 | 4.34 |
| Bireswar Das | 2 | 66 | 10.61 |
| Johannes Köbler | 3 | 580 | 46.51 |
| Sebastian Kuhnert | 4 | 36 | 6.52 |