Name
Abstract | ||
|---|---|---|
We prove that the graph isomorphism problem restricted to trees and to colored graphs with color multiplicities 2 and 3 is many-one complete for several complexity classes within NC2. In particular we show that tree isomorphism, when trees are encoded as strings, is NC1-hard under AC0-reductions. NC1- completeness thus follows from Buss's NC1 upper bound. By contrast, we prove that testing isomorphism of two trees encoded as pointer lists is L-complete. Concerning colored graphs we show that the isomorphism problem for graphs with color multiplicities 2 and 3 is complete for symmetric logarithmic space SL under many-one reductions. This result improves the existing upper bounds for the problem. We also show that the graph automorphism problem for colored graphs with color classes of size 2 is equivalent to deciding whether a graph has more than a single connected component and we prove that for color classes of size 3 the graph automorphism problem is contained in SL. |
Year | DOI | Venue |
|---|---|---|
2003 | 10.1016/S0022-0000(03)00042-4 | J. Comput. Syst. Sci. |
Keywords | Field | DocType |
testing isomorphism,existing upper bound,symmetric logarithmic space sl,color multiplicity,many-one reduction,graph isomorphism problem,isomorphism problem,color class,completeness result,tree isomorphism,graph automorphism problem,graph isomorphism,complexity class | Graph automorphism,Graph canonization,Discrete mathematics,Combinatorics,Graph property,Graph isomorphism,Graph homomorphism,Induced subgraph isomorphism problem,Symmetric graph,Subgraph isomorphism problem,Mathematics | Journal |
Volume | Issue | ISSN |
66 | 3 | Journal of Computer and System Sciences |
Citations | PageRank | References |
27 | 0.98 | 19 |
Authors | ||
4 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Birgit Jenner | 1 | 247 | 14.47 |
| Johannes Köbler | 2 | 580 | 46.51 |
| P. McKenzie | 3 | 152 | 8.23 |
| Jacobo Torán | 4 | 564 | 49.26 |