Canonizing Graphs of Bounded Tree Width in Logspace

DOI10.1145/3132720MaRDI QIDQ4973889zbMATH OpenOpenAlexFDO

Authors Michael Elberfeld, P. Schweitzer

Publication date 6 December 2019

Published in ACM Transactions on Computation Theory (Search for Journal in Brave)

Full work available at URL https://drops.dagstuhl.de/opus/volltexte/2016/5733/

zbMATH Keywords

algorithmic graph theorycomputational complexitygraph canonizationgraph isomorphismlogspace algorithmstree width

Mathematics Subject Classification ID

Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10)

Recommendations

• Canonizing graphs of bounded tree width in logspace
• Graphs of bounded treewidth can be canonized in AC^1
• Fixed-Parameter Tractable Canonization and Isomorphism Test for Graphs of Bounded Treewidth
• scientific article; zbMATH DE number 932194
• Bounded tree-width and LOGCFL
• Bounded Tree-Width and LOGCFL
• A managed Bayesian risk approach for decision making alternatives
• scientific article; zbMATH DE number 4121424
• Tree-Width and Optimization in Bounded Degree Graphs
• scientific article; zbMATH DE number 1982177

Cited in

(23)

• 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
• Interval graphs: canonical representation in logspace
• Bounded Tree-Width and LOGCFL
• scientific article; zbMATH DE number 1088188 (Why is no real title available?)
• Around and beyond the isomorphism problem for interval graphs
• Canonizing graphs of bounded tree width in logspace
• An improved isomorphism test for bounded-tree-width graphs
• An improved isomorphism test for bounded-tree-width graphs
• Computing Tree Decompositions
• Logspace and FPT algorithms for graph isomorphism for subclasses of bounded tree-width graphs
• Embedding and canonizing graphs of bounded genus in logspace
• Count-free Weisfeiler-Leman and group isomorphism
• On the parallel complexity of group isomorphism via Weisfeiler-Leman
• Canonizing graphs of bounded rank-width in parallel via Weisfeiler-Leman
• The isomorphism problem for \(k\)-trees is complete for logspace
• Restricted space algorithms for isomorphism on bounded treewidth graphs
• Finite variable counting logics with restricted requantification
• 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 Q4973889)