Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > KEYWORD > CANONICAL LABELING:
Reports tagged with Canonical Labeling:
TR11-032 | 11th March 2011
Fabian Wagner

Graphs of Bounded Treewidth can be Canonized in AC$^1$

In recent results the complexity of isomorphism testing on
graphs of bounded treewidth is improved to TC$^1$ [GV06] and further to LogCFL [DTW10].
The computation of canonical forms or a canonical labeling provides more information than
isomorphism testing.
Whether canonization is in NC or even TC$^1$ was stated ... more >>>




ISSN 1433-8092 | Imprint