Isomorphism testing for graphs excluding small topological subgraphs

DOI10.1145/3651986MaRDI QIDQ7023548zbMATH OpenFDO

Authors Daniel Neuen

Publication date 21 February 2025

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

Full work available at URL https://doi.org/10.1145/3651986

zbMATH Keywords

automorphism groupsgraph isomorphismtopological subgraphsWeisfeiler-Leman algorithm

Mathematics Subject Classification ID

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)

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
• An optimal lower bound on the number of variables for graph identification
• Graph isomorphism for unit square graphs
• Graph isomorphism in quasipolynomial time (extended abstract)
• scientific article; zbMATH DE number 706263 (Why is no real title available?)
• scientific article; zbMATH DE number 3815 (Why is no real title available?)
• scientific article; zbMATH DE number 1849958 (Why is no real title available?)
• scientific article; zbMATH DE number 894528 (Why is no real title available?)
• Hypergraph Isomorphism for Groups with Restricted Composition Factors
• 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 Graphs Excluding Small Minors
• Isomorphism testing for graphs of bounded rank width
• On construction and identification of graphs. With contributions by A. Lehman, G. M. Adelson-Velsky, V. Arlazarov, I. Faragev, A. Uskov, I. Zuev, M. Rosenfeld and B. Weisfeiler
• On the orders of primitive groups with restricted nonabelian composition factors
• Polynomial algorithms for graph isomorphism and chromatic index on partial k-trees
• Proof of a conjecture of Mader, Erdős and Hajnal on topological complete subgraphs
• Recent advances on the graph isomorphism problem
• Reducibility among combinatorial problems
• Structure theorem and isomorphism test for graphs with excluded topological subgraphs
• The isomorphism problem for classes of graphs closed under contraction
• The power of the Weisfeiler-Leman algorithm to decompose graphs
• The Weisfeiler--Leman Dimension of Planar Graphs Is at Most 3
• Tight lower and upper bounds for the complexity of canonical colour refinement
• Topological cliques in graphs II

Cited in

(1)

• The iteration number of the Weisfeiler-Leman algorithm

This page was built for publication: Isomorphism testing for graphs excluding small topological subgraphs

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