An improved isomorphism test for bounded-tree-width graphs

DOI10.1145/3382082MaRDI QIDQ4987453zbMATH OpenOpenAlexFDO

Authors Martin Grohe, Daniel Neuen, P. Schweitzer, 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

decompositionsgraph canonizationgraph isomorphismtree-width

Mathematics Subject Classification ID

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

Recommendations

• An improved isomorphism test for bounded-tree-width graphs
• Fixed-Parameter Tractable Canonization and Isomorphism Test for Graphs of Bounded Treewidth
• Restricted space algorithms for isomorphism on bounded treewidth graphs
• Logspace and FPT algorithms for graph isomorphism for subclasses of bounded tree-width graphs
• Canonizing Graphs of Bounded Tree Width in Logspace

Cited in

(17)

• Fixed-Parameter Tractable Canonization and Isomorphism Test for Graphs of Bounded Treewidth
• Isomorphism for graphs of bounded feedback vertex set number
• An improved isomorphism test for bounded-tree-width graphs
• Recent advances on the graph isomorphism problem
• Canonisation and Definability for Graphs of Bounded Rank Width
• Isomorphism Testing for Graphs Excluding Small Minors
• Order Reconfiguration under Width Constraints
• A Faster Isomorphism Test for Graphs of Small Degree
• Isomorphism Testing Parameterized by Genus and Beyond
• Faster isomorphism for p-groups of class 2 and exponent p
• Testing isomorphism of chordal graphs of bounded leafage is fixed-parameter tractable
• Canonizing graphs of bounded rank-width in parallel via Weisfeiler-Leman
• Solution-hashing search based on layout-graph transformation for unequal circle packing
• Isomorphism testing for graphs excluding small topological subgraphs
• Automorphisms and isomorphisms of maps in linear time
• The isomorphism problem of power graphs and a question of Cameron
• Isomorphism testing of k-trees is in NC, for fixed k

This page was built for publication: An improved isomorphism test for bounded-tree-width graphs

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