2026-07-20T09:01:39Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:5733 2024-03-06T10:36:57Z ddc:004 open_access

Canonizing Graphs of Bounded Tree Width in Logspace Elberfeld, Michael Schweitzer, Pascal algorithmic graph theory computational complexity graph isomorphism logspace tree width 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Michael Elberfeld and Pascal Schweitzer 2016 Is Part Of LIPIcs, Volume 47, 33rd Symposium on Theoretical Aspects of Computer Science (STACS 2016) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.STACS.2016.32 urn:nbn:de:0030-drops-57336 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2016.32 eng https://creativecommons.org/licenses/by/3.0/legalcode