Isomorphism Testing Parameterized by Genus and Beyond

DOI10.1137/22M1514076MaRDI QIDQ6188514zbMATH OpenOpenAlexFDO

Authors 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

Euler genusfixed-parameter tractabilitygraph isomorphismWeisfeiler-Leman algorithm

Mathematics Subject Classification ID

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

Cites work

• A note on the graph isomorphism counting problem
• 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
• Das Geschlecht des vollständigen paaren Graphen
• Fixed-Parameter Tractable Canonization and Isomorphism Test for Graphs of Bounded Treewidth
• Graph isomorphism in quasipolynomial time (extended abstract)
• scientific article; zbMATH DE number 5485559 (Why is no real title available?)
• 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 graphs which are pairwise k-separable
• Isomorphism of planar graphs (working paper)
• Isomorphism Testing for Graphs Excluding Small Minors
• 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
• Parameterized algorithms
• Parametrized complexity theory.
• Polynomial algorithms for graph isomorphism and chromatic index on partial k-trees
• 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

Cited in

(3)

• Testing isomorphism of chordal graphs of bounded leafage is fixed-parameter tractable
• Bounding the Weisfeiler-Leman dimension via a depth analysis of I/R-trees
• The iteration number of the Weisfeiler-Leman algorithm

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

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