2019/12/21 by Ilia Ponomarenko, Andrey Vasil'ev, Andrey Vasil’ev · 10 citations
Computer Science · Mathematics · #Advanced Combinatorial Mathematics #Cyclic permutation #Finite Group Theory Research #Group (periodic table) #Homotopy and Cohomology in Algebraic Topology #Partial permutation #Permutation (music) #Permutation graph #Permutation group #Polynomial #Time complexity #acm:05E18 #acm:20B25 #cs.CC #math.CO #math.GR #msc:05E18 #msc:20B25
paper · pdf · doi:10.1007/s00037-020-00195-7
published in Computational Complexity 29(1) (Birkhäuser) · 20 pages
arxiv created 2019/12/21 · openalex created_date 2019/12/26 · openalex publication_date 2020/06/01 · arxiv updated 2021/07/06 · openalex updated_date 2026/08/05
The 2-closure G of a permutation group G on Ω is defined to be the largest permutation group on Ω, having the same orbits on Ω×Ω as G. It is proved that if G is supersolvable, then G can be found in polynomial time in |Ω|. As a byproduct of our technique, it is shown that the composition factors of G are cyclic or alternating of prime degree.