The Complexity of Graph Isomorphism for Colored Graphs with Color Classes of Size 2 and 3
The Complexity of Graph Isomorphism for Colored Graphs with Color Classes of Size 2 and 3
Johannes Köbler and Jacobo Torán
Abstract:
Abstract:
We prove that the graph isomorphism problem restricted to colored 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 an undirected 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.
Ps-File: The Complexity of Graph Isomorphism for Colored Graphs with Color Classes of Size 2 and 3
zuletzt geändert:
31.10.05
SV
Document Actions
Persönliche Werkzeuge
- Sie sind nicht eingeloggt.
- Seite bearbeiten
Deutsch
English