Canonizing graphs of bounded tree width in logspace

DOI10.4230/LIPICS.STACS.2016.32MaRDI QIDQ4601884zbMATH OpenOpenAlexFDO

Authors Michael Elberfeld, P. Schweitzer

Publication date 24 January 2018

Full work available at URL https://arxiv.org/abs/1506.07810

zbMATH Keywords

algorithmic graph theorycomputational complexitygraph isomorphismlogspacetree width

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10)

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 by logarithmic-space (logspace) algorithms. 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 class 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.

Recommendations

• Canonizing Graphs of Bounded Tree Width in Logspace
• Graphs of bounded treewidth can be canonized in AC^1
• Restricted space algorithms for isomorphism on bounded treewidth graphs
• Restricted space algorithms for isomorphism on bounded treewidth graphs
• A Logspace Algorithm for Partial 2-Tree Canonization

Cited in

(20)

• A gentle introduction to applications of algorithmic metatheorems for space and circuit classes
• Frameworks for designing in-place graph algorithms
• Biconnectivity, \(st\)-numbering and other applications of DFS using \(O(n)\) bits
• Fixed-Parameter Tractable Canonization and Isomorphism Test for Graphs of Bounded Treewidth
• Graphs of bounded treewidth can be canonized in AC^1
• Restricted space algorithms for isomorphism on bounded treewidth graphs
• The Isomorphism Problem for k-Trees Is Complete for Logspace
• A Logspace Algorithm for Partial 2-Tree Canonization
• From Invariants to Canonization in Parallel
• Bounded Tree-Width and LOGCFL
• scientific article; zbMATH DE number 6970796 (Why is no real title available?)
• Canonizing Graphs of Bounded Tree Width in Logspace
• An improved isomorphism test for bounded-tree-width graphs
• A framework for in-place graph algorithms
• Logspace and FPT algorithms for graph isomorphism for subclasses of bounded tree-width graphs
• Embedding and canonizing graphs of bounded genus in logspace
• Graph isomorphism restricted by lists
• The isomorphism problem for \(k\)-trees is complete for logspace
• Restricted space algorithms for isomorphism on bounded treewidth graphs
• On parse trees and Myhill-Nerode-type tools for handling graphs of bounded rank-width

This page was built for publication: Canonizing graphs of bounded tree width in logspace

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4601884)