Subcomplete generalizations of graph isomorphism

DOI10.1016/0022-0000(82)90015-0zbMath0508.68044MaRDI 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 complexity; graph isomorphism; isomorphism complete; group intersection

Mathematics Subject Classification ID

68Q25: Analysis of algorithms and problem complexity

20B25: Finite automorphism groups of algebraic, geometric, or combinatorial structures

68R10: Graph theory (including graph drawing) in computer science

Related Items

Graph isomorphism is low for PP, Some recognition problems related to graph isomorphism

Cites Work

• 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)
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item