An Improved Isomorphism Test for Bounded-tree-width Graphs

DOI10.1145/3382082zbMath1484.68161OpenAlexW3033022049MaRDI QIDQ4987453

Pascal Schweitzer, Daniel Neuen, Martin Grohe, Daniel Wiebking

Publication date: 3 May 2021

Published in: ACM Transactions on Algorithms (Search for Journal in Brave)

Full work available at URL: https://drops.dagstuhl.de/opus/volltexte/2018/9071/

zbMATH Keywords

decompositionstree-widthgraph isomorphismgraph canonization

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Graph theory (including graph drawing) in computer science (68R10) Graphs and abstract algebra (groups, rings, fields, etc.) (05C25) Graph algorithms (graph-theoretic aspects) (05C85) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60)

Related Items (4)

Isomorphism Testing for Graphs Excluding Small Minors ⋮ Order Reconfiguration under Width Constraints ⋮ Isomorphism Testing Parameterized by Genus and Beyond ⋮ Canonisation and Definability for Graphs of Bounded Rank Width

This page was built for publication: An Improved Isomorphism Test for Bounded-tree-width Graphs