An improved isomorphism test for bounded-tree-width graphs

DOI10.4230/LIPIcs.ICALP.2018.67zbMath1484.68162arXiv1803.06858OpenAlexW2963366865MaRDI QIDQ5002745

Daniel Neuen, Daniel Wiebking, Pascal Schweitzer, Martin Grohe

Publication date: 28 July 2021

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

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 (8)

Graph isomorphism for \((H_1, H_2)\)-free graphs: an almost complete dichotomy ⋮ Computing Autotopism Groups of Partial Latin Rectangles ⋮ A Faster Isomorphism Test for Graphs of Small Degree ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Bottom-up unranked tree-to-graph transducers for translation into semantic graphs ⋮ An adaptive prefix-assignment technique for symmetry reduction ⋮ Treewidth of display graphs: bounds, brambles and applications

Cites Work

• Unnamed Item
• Isomorphism of graphs of bounded valence can be tested in polynomial time
• A note on the graph isomorphism counting problem
• Optimal decomposition by clique separators
• Fixed-Parameter Tractable Canonization and Isomorphism Test for Graphs of Bounded Treewidth
• Reduction Techniques for Graph Isomorphism in the Context of Width Parameters
• Polynomial algorithms for graph isomorphism and chromatic index on partial k-trees
• Canonizing Graphs of Bounded Tree Width in Logspace
• Graph Isomorphism for unit square graphs
• Structure Theorem and Isomorphism Test for Graphs with Excluded Topological Subgraphs
• Graph isomorphism in quasipolynomial time [extended abstract]

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