Name
Abstract | ||
|---|---|---|
We prove that the tree isomorphism problem, when trees are encoded as strings, is NC1-hard under DLOGTIME-reductions. NC1 -completeness thus follows from Buss's recent NC1 upper bound. By contrast, we prove that testing isomorphism of two trees encoded as pointer lists is L-complete |
Year | DOI | Venue |
|---|---|---|
1998 | 10.1109/CCC.1998.694595 | IEEE Conference on Computational Complexity |
Keywords | Field | DocType |
computational complexity,formal languages,trees (mathematics),DLOGTIME-reductions,L-complete,NC1-completeness,NC1-hard,hardness,isomorphism,tree isomorphism,upper bound | Discrete mathematics,Pointer (computer programming),Combinatorics,Tree (graph theory),Polynomial,Upper and lower bounds,Turing machine,Isomorphism,Mathematics,Computational complexity theory | Conference |
ISSN | ISBN | Citations |
1093-0159 | 0-8186-8395-3 | 8 |
PageRank | References | Authors |
0.58 | 7 | 3 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Birgit Jenner | 1 | 247 | 14.47 |
| P. McKenzie | 2 | 152 | 8.23 |
| Jacobo Torán | 3 | 8 | 0.58 |