Subcomplete generalizations of graph isomorphism

DOI10.1016/0022-0000(82)90015-0zbMath0508.68044OpenAlexW2031113708MaRDI QIDQ1838044

Christoph M. Hoffmann

Publication date: 1982

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

Full work available at URL: https://doi.org/10.1016/0022-0000(82)90015-0

zbMATH Keywords

computational complexitygraph isomorphismisomorphism completegroup intersection

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Finite automorphism groups of algebraic, geometric, or combinatorial structures (20B25) Graph theory (including graph drawing) in computer science (68R10)

Related Items

Some recognition problems related to graph isomorphism, A subquadratic algorithm for the simultaneous conjugacy problem, Fast computation of the centralizer of a permutation group in the symmetric group, Computing stable epimorphisms onto finite groups, Graph isomorphism is low for PP, The simultaneous conjugacy problem in the symmetric group, Graph isomorphism is low for PP

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Computing the composition factors of a permutation group in polynomial time
• The complexity of computing the permanent
• Isomorphism of graphs of bounded valence can be tested in polynomial time
• A note on the graph isomorphism counting problem
• A V log V algorithm for isomorphism of triconnected planar graphs
• Constructive graph labeling using double cosets
• Some NP-Complete Problems Similar to Graph Isomorphism
• On the Structure of Polynomial Time Reducibility
• Isomorphism Testing for Graphs, Semigroups, and Finite Automata are Polynomially Equivalent Problems
• On the n^{log n} isomorphism technique (A Preliminary Report)