Isomorphism Testing Parameterized by Genus and Beyond

DOI10.1137/22m1514076OpenAlexW3176154105MaRDI QIDQ6188514

Daniel Neuen

Publication date: 7 February 2024

Published in: SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/22m1514076

zbMATH Keywords

fixed-parameter tractabilitygraph isomorphismEuler genusWeisfeiler-Leman algorithm

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Nonnumerical algorithms (68W05) Graph theory (including graph drawing) in computer science (68R10) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• On the orders of primitive groups with restricted nonabelian composition factors
• Isomorphism of graphs of bounded valence can be tested in polynomial time
• The isomorphism problem for classes of graphs closed under contraction
• An optimal lower bound on the number of variables for graph identification
• 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
• A note on the graph isomorphism counting problem
• Das Geschlecht des vollständigen paaren Graphen
• Parametrized complexity theory.
• Fixed-Parameter Tractable Canonization and Isomorphism Test for Graphs of Bounded Treewidth
• Polynomial algorithms for graph isomorphism and chromatic index on partial k-trees
• Isomorphism of graphs which are pairwise k-separable
• An Improved Isomorphism Test for Bounded-tree-width Graphs
• Reducibility among Combinatorial Problems
• Isomorphism of Planar Graphs (Working Paper)
• A unifying method for the design of algorithms canonizing combinatorial objects
• Structure Theorem and Isomorphism Test for Graphs with Excluded Topological Subgraphs
• Graph isomorphism in quasipolynomial time [extended abstract]
• Parameterized Algorithms
• Isomorphism Testing for Graphs Excluding Small Minors
• Hypergraph Isomorphism for Groups with Restricted Composition Factors

This page was built for publication: Isomorphism Testing Parameterized by Genus and Beyond