文章基本信息

标题：Canonizing Graphs of Bounded Tree Width in Logspace
本地全文：下载
作者：Michael Elberfeld ; Pascal Schweitzer
期刊名称：LIPIcs : Leibniz International Proceedings in Informatics
电子版ISSN：1868-8969
出版年度：2016
卷号：47
页码：32:1-32:14
DOI：10.4230/LIPIcs.STACS.2016.32
出版社：Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
摘要：Graph canonization is the problem of computing a unique representative, a canon, from the isomorphism class of a given graph. This implies that two graphs are isomorphic exactly if their canons are equal. We show that graphs of bounded tree width can be canonized in deterministic logarithmic space (logspace). This implies that the isomorphism problem for graphs of bounded tree width can be decided in logspace. In the light of isomorphism for trees being hard for the complexity class logspace, this makes the ubiquitous classes of graphs of bounded tree width one of the few classes of graphs for which the complexity of the isomorphism problem has been exactly determined.
关键词：algorithmic graph theory; computational complexity; graph isomorphism; logspace; tree width