Graph isomorphism, general remarks

DOI10.1016/0022-0000(79)90043-6MaRDI QIDQ1255944zbMATH OpenOpenAlexFDO

Authors Gary L. 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

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

Cites work

• Automorphisms of graphs and coverings
• Dividing a Graph into Triconnected Components
• scientific article; zbMATH DE number 3566230 (Why is no real title available?)
• scientific article; zbMATH DE number 3571502 (Why is no real title available?)
• scientific article; zbMATH DE number 3445271 (Why is no real title available?)
• scientific article; zbMATH DE number 3430698 (Why is no real title available?)
• scientific article; zbMATH DE number 3236772 (Why is no real title available?)
• scientific article; zbMATH DE number 3305097 (Why is no real title available?)
• scientific article; zbMATH DE number 3198885 (Why is no real title available?)
• scientific article; zbMATH DE number 3046496 (Why is no real title available?)
• Isomorphism Testing for Graphs, Semigroups, and Finite Automata are Polynomially Equivalent Problems
• On full embeddings of categories of algebras
• On regular graphs, V
• On the \(n\log{n}\) isomorphism technique (preliminary report)
• On the Symmetry of Cubic Graphs
• Parallel concepts in graph theory
• Riemann's hypothesis and tests for primality

Cited in

(22)

• Graph isomorphism problem
• Two reductions of graph isomorphism to problems on polynomials
• Isomorphism of graphs of bounded valence can be tested in polynomial time
• Deep graph similarity learning: a survey
• On the complexity of recognizing Wheeler graphs
• Compatible topologies on graphs: an application to graph isomorphism problem complexity
• Linear time algorithms for Abelian group isomorphism and related problems
• Computational group theory. Abstracts from the workshop held August 15--21, 2021 (hybrid meeting)
• The complexity of computing the automorphism group of automata and related problems
• Using local similarity measures to efficiently address approximate graph matching
• On Borel complexity of the isomorphism problems for graph related classes of Lie algebras and finite p-groups
• Beating the generator-enumeration bound for \(p\)-group isomorphism
• A fast isomorphism test for groups whose Lie algebra has genus 2
• On the Hardness and Inapproximability of Recognizing Wheeler Graphs
• Linear and sublinear time algorithms for the basis of abelian groups
• 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
• Graph isomorphism in quasipolynomial time parameterized by treewidth
• Testing equivalence to design polynomials
• Quantum mechanics on finite groups
• Functional graphs of polynomials over finite fields

This page was built for publication: Graph isomorphism, general remarks

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