文章基本信息

标题：Graphs of Bounded Treewidth can be Canonized in AC1
本地全文：下载
作者：Fabian Wagner
期刊名称：Electronic Colloquium on Computational Complexity
印刷版ISSN：1433-8092
出版年度：2011
卷号：2011
出版社：Universität Trier, Lehrstuhl für Theoretische Computer-Forschung
摘要：In recent results the complexity of isomorphism testing on graphs of bounded treewidth is improved to TC1 [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 TC1 was stated as an open question in [Köb06]. Köbler and Verbitsky [KV08] give a TC2 canonical labeling algorithm. We show that a canonical labeling can be computed in AC1. This is based on several ideas, e.g. that approximate tree decompositions of logarithmic depth can be obtained in logspace [EJT10], and techniques of Lindells tree canonization algorithm [Lin92]. We define recursively what we call a minimal description which gives with respect to some parameters in a logarithmic number of levels a canonical invariant together with an arrangement of all vertices. From this we compute a canonical labeling.
关键词：Bounded Treewidth, Canonical Labeling, Canonization