Permutation Groups and the Graph Isomorphism Problem

DOI10.1007/978-3-319-05446-9_11MaRDI QIDQ2821703zbMATH OpenOpenAlexFDO

Authors Sumanta Ghosh, Piyush P. Kurur

Publication date 22 September 2016

Published in Perspectives in Computational Complexity (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-319-05446-9_11

zbMATH Keywords

algorithmsfinite permutation groupsgraph isomorphisms

Mathematics Subject Classification ID

Graphs and abstract algebra (groups, rings, fields, etc.) (05C25) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60) Finite automorphism groups of algebraic, geometric, or combinatorial structures (20B25) Analysis of algorithms and problem complexity (68Q25)

Recommendations

• Graph isomorphism problem and 2-closed permutation groups
• On a permutability problem for groups.
• Graph representation of permutation groups. I.
• On permutability graphs of subgroups of groups
• On permutable cyclic graph of finite groups.
• Regular permutation groups and Cayley graphs.
• On a graph related to permutability in finite groups
• On graph-restrictive permutation groups
• Algorithms for permutability in finite groups.
• Permutation groups: theory and applications.

Cites work

• A note on the graph isomorphism counting problem
• A polynomial bound for the orders of primitive solvable groups
• Does co-NP have short interactive proofs ?
• Graph isomorphism problem
• Graphs and finite permutation groups
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 477971 (Why is no real title available?)
• scientific article; zbMATH DE number 3223737 (Why is no real title available?)
• Isomorphism of graphs of bounded valence can be tested in polynomial time
• On the orders of primitive groups with restricted nonabelian composition factors
• On the Structure of Polynomial Time Reducibility

Cited in

(11)

• Permutation group approach to association schemes
• Graph isomorphism problem and 2-closed permutation groups
• Representability of permutation representations on coalgebras and the isomorphism problem
• Representing Groups on Graphs
• scientific article; zbMATH DE number 475362 (Why is no real title available?)
• scientific article; zbMATH DE number 635801 (Why is no real title available?)
• Representing equivalence problems for combinatorial objects
• GROUP, GRAPHS, ALGORITHMS: THE GRAPH ISOMORPHISM PROBLEM
• Graph isomorphism in quasipolynomial time (extended abstract)
• Graph representation of permutation groups. I.
• Computational complexity of computing symmetries in finite-domain planning

This page was built for publication: Permutation Groups and the Graph Isomorphism Problem

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