Graph isomorphism in quasipolynomial time parameterized by treewidth

DOI10.4230/LIPICS.ICALP.2020.103MaRDI QIDQ6842467zbMATH OpenFDO

Authors Daniel Wiebking

Publication date 18 March 2026

Copyright license Creative Commons Attribution 3.0 Unported

Full work available at URL https://doi.org/10.4230/LIPICS.ICALP.2020.103

zbMATH Keywords

canonizationgraph isomorphismhypergraphstreewidth

Mathematics Subject Classification ID

Theory of software (68Nxx) Theory of computing (68Qxx)

Cites work

• A\,V^ 2 algorithm for determining isomorphism of planar graphs
• A faster isomorphism test for graphs of small degree
• A unifying method for the design of algorithms canonizing combinatorial objects
• An improved isomorphism test for bounded-tree-width graphs
• Canonical form for graphs in quasipolynomial time: preliminary report
• Errors in graph embedding algorithms
• Fixed-Parameter Tractable Canonization and Isomorphism Test for Graphs of Bounded Treewidth
• Fundamentals of parameterized complexity
• Graph isomorphism in quasipolynomial time (extended abstract)
• Graph isomorphism is in the low hierarchy
• Graph isomorphism problem
• Graph isomorphism, general remarks
• Graph minors. I. Excluding a forest
• scientific article; zbMATH DE number 5485559 (Why is no real title available?)
• scientific article; zbMATH DE number 1849958 (Why is no real title available?)
• Hypergraph isomorphism for groups with restricted composition factors
• Isomorphism for graphs of bounded connected-path-distance-width
• Isomorphism for graphs of bounded distance width
• Isomorphism for graphs of bounded feedback vertex set number
• Isomorphism of graphs of bounded valence can be tested in polynomial time
• Isomorphism of k-contractible graphs. A generalization of bounded valence and bounded genus
• Isomorphism testing for embeddable graphs through definability
• Normalizes and permutational isomorphisms in simply-exponential time
• On tractable parameterizations of graph isomorphism
• Optimal decomposition by clique separators
• Polynomial algorithms for graph isomorphism and chromatic index on partial k-trees
• Structure theorem and isomorphism test for graphs with excluded topological subgraphs
• The isomorphism problem for classes of graphs closed under contraction

Cited in

(2)

• Testing isomorphism of chordal graphs of bounded leafage is fixed-parameter tractable
• The isomorphism problem of power graphs and a question of Cameron

This page was built for publication: Graph isomorphism in quasipolynomial time parameterized by treewidth

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