Graph isomorphism, general remarks

DOI10.1016/0022-0000(79)90043-6zbMath0403.03029OpenAlexW2017265236MaRDI QIDQ1255944

Gary Lee Miller

Publication date: 1979

Published in: Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL: http://hdl.handle.net/1802/13806

zbMATH Keywords

Graph Isomorphism ProblemIsomorphisms of Finite GroupsPolynomial Time ReducibilitiesSymmetric Cubic Graph Nonisomorphism

Mathematics Subject Classification ID

Graphs and abstract algebra (groups, rings, fields, etc.) (05C25) Decidability of theories and sets of sentences (03B25) Complexity of computation (including implicit computational complexity) (03D15)

Related Items

Linear time algorithms for Abelian group isomorphism and related problems, Quantum mechanics on finite groups, Functional graphs of polynomials over finite fields, A Faster Isomorphism Test for Graphs of Small Degree, Data Structures for Topologically Sound Higher-Dimensional Diagram Rewriting, The road problem and homomorphisms of directed graphs, Computational group theory. Abstracts from the workshop held August 15--21, 2021 (hybrid meeting), Two reductions of graph isomorphism to problems on polynomials, Isomorphism of graphs of bounded valence can be tested in polynomial time, The complexity of computing the automorphism group of automata and related problems, Using local similarity measures to efficiently address approximate graph matching, Beating the generator-enumeration bound for \(p\)-group isomorphism, A fast isomorphism test for groups whose Lie algebra has genus 2, Linear and sublinear time algorithms for the basis of abelian groups, Compatible topologies on graphs: an application to graph isomorphism problem complexity, Deep graph similarity learning: a survey, On the Hardness and Inapproximability of Recognizing Wheeler Graphs, On Borel complexity of the isomorphism problems for graph related classes of Lie algebras and finite p-groups, Graph isomorphism problem, On the complexity of recognizing Wheeler graphs

Cites Work

• On regular graphs, V
• Riemann's hypothesis and tests for primality
• Parallel concepts in graph theory
• Automorphisms of graphs and coverings
• On full embeddings of categories of algebras
• On the Symmetry of Cubic Graphs
• Isomorphism Testing for Graphs, Semigroups, and Finite Automata are Polynomially Equivalent Problems
• Dividing a Graph into Triconnected Components
• On the n^{log n} isomorphism technique (A Preliminary Report)
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item