Name
Abstract | ||
|---|---|---|
We show that isomorphism testing of k-trees is in the class StUSPACE(log n) (strongly unambiguous logspace). This bound follows from a deterministic logspace algorithm that accesses a strongly unambiguous logspace oracle for canonizing k-trees. Further we give a logspace canonization algorithm for k-paths. |
Year | DOI | Venue |
|---|---|---|
2007 | 10.1007/978-3-540-77120-3_71 | ISAAC |
Keywords | Field | DocType |
canonizing k-trees,unambiguous logspace oracle,isomorphism testing,logspace canonization algorithm,class stuspace,deterministic logspace algorithm,log n,space complexity,k-tree isomorphism,unambiguous logspace | L,Binary logarithm,Discrete mathematics,Combinatorics,K-tree,Oracle,Isomorphism,Mathematics | Conference |
Volume | ISSN | ISBN |
4835 | 0302-9743 | 3-540-77118-2 |
Citations | PageRank | References |
7 | 0.50 | 23 |
Authors | ||
3 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| V. Arvind | 1 | 52 | 4.34 |
| Bireswar Das | 2 | 66 | 10.61 |
| Johannes Köbler | 3 | 580 | 46.51 |