The graph isomorphism problem and approximate categories

DOI10.1016/j.jsc.2013.06.002zbMath1283.05183arXiv1012.2081MaRDI QIDQ2437326

H. G. J. Derksen

Publication date: 3 March 2014

Published in: Journal of Symbolic Computation (Search for Journal in Brave)

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

zbMATH Keywords

categories; complexity theory; graph isomorphism problem; Weisfeiler-Lehman algorithm

Mathematics Subject Classification ID

68Q25: Analysis of algorithms and problem complexity

05C85: Graph algorithms (graph-theoretic aspects)

05C60: Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.)

Related Items

Unnamed Item

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• The complexity of computing the permanent
• Coherent algebras and the graph isomorphism problem
• Testing isomorphism of modules.
• Coherent algebras
• Isomorphism of graphs of bounded valence can be tested in polynomial time
• 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
• On highly closed cellular algebras and highly closed isomorphisms
• On a new high dimensional Weisfeiler-Lehman algorithm
• Cellular algebras
• A V log V algorithm for isomorphism of triconnected planar graphs
• Geometric Complexity Theory I: An Approach to thePvs.NPand Related Problems
• Geometric Complexity Theory II: Towards Explicit Obstructions for Embeddings among Class Varieties