Paper Info
Title
Canonizing Graphs of Bounded Tree Width in Logspace.
Abstract
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.
Year
DOI
Venue
2016
10.1145/3132720
STACS
Keywords
DocType
Volume
Algorithmic graph theory,computational complexity,graph canonization,graph isomorphism,logspace algorithms,tree width
Conference
abs/1506.07810
Issue
ISSN
Citations 
3
1942-3454
9
PageRank 
References 
Authors
0.48
19
2
Name
Order
Citations
PageRank
Michael Elberfeld111510.63
Pascal Schweitzer221416.94