Graph isomorphism problem and 2-closed permutation groups

DOI10.1007/BF01196622MaRDI QIDQ1311608zbMATH OpenFDO

Authors Ilya Ponomarenko

Publication date 4 January 1995

Published in Applicable Algebra in Engineering, Communication and Computing (Search for Journal in Brave)

zbMATH Keywords

polynomial time algorithmcoherent configurations2-closed permutation groupsgraph isomorphism problemalgorithmic problems2-closurestrong generating setnilpotent permutation group

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graphs and abstract algebra (groups, rings, fields, etc.) (05C25) General theory for finite permutation groups (20B05) Finite automorphism groups of algebraic, geometric, or combinatorial structures (20B25) Sylow subgroups, Sylow properties, (pi)-groups, (pi)-structure (20D20) Generators, relations, and presentations of groups (20F05)

Recommendations

• Two-closure of rank \(3\) groups in polynomial time
• Two-closure of odd permutation group in polynomial time
• scientific article; zbMATH DE number 96386
• The 2-closure of a \(\frac{3}{2}\)-transitive group in polynomial time
• Permutation Groups and the Graph Isomorphism Problem

Cites work

• scientific article; zbMATH DE number 3841910 (Why is no real title available?)
• scientific article; zbMATH DE number 3991749 (Why is no real title available?)
• scientific article; zbMATH DE number 3223737 (Why is no real title available?)
• A note on the graph isomorphism counting problem
• A polynomial bound for the orders of primitive solvable groups
• Isomorphism of graphs of bounded valence can be tested in polynomial time
• On the 2-Closures of Finite Permutation Groups
• Polynomial time recognition and isomorphism testing for cyclic tournaments
• Sylow's theorem in polynomial time

Cited in

(11)

• Two-closure of odd permutation group in polynomial time
• The 2-closure of a \(\frac{3}{2}\)-transitive group in polynomial time
• On the asymmetric complexity of the group-intersection problem
• Finite nilpotent groups that coincide with their 2-closures in all of their faithful permutation representations
• Two-closure of rank \(3\) groups in polynomial time
• GROUP, GRAPHS, ALGORITHMS: THE GRAPH ISOMORPHISM PROBLEM
• On computing the closures of solvable permutation groups
• Permutation Groups and the Graph Isomorphism Problem
• Two-closures of supersolvable permutation groups in polynomial time
• Closures of finite permutation groups
• On finite totally \(2\)-closed groups

This page was built for publication: Graph isomorphism problem and \(2\)-closed permutation groups

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