Parallel algorithms for solvable permutation groups

DOI10.1016/0022-0000(88)90044-XzbMath0657.68043MaRDI QIDQ1111023

Eugene M. Luks, Pierre McKenzie

Publication date: 1988

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

zbMATH Keywords

nilpotent groupsparallel algorithmsparallel complexityautomorphism of graphspower commutator basissolvable permutation groups

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Finite solvable groups, theory of formations, Schunck classes, Fitting classes, (pi)-length, ranks (20D10) Series and lattices of subgroups (20D30) Generators, relations, and presentations of groups (20F05) Graphs and abstract algebra (groups, rings, fields, etc.) (05C25) Software, source code, etc. for problems pertaining to group theory (20-04) General theory for finite permutation groups (20B05)

Related Items (5)

Constrained synchronization and subset synchronization problems for weakly acyclic automata ⋮ Membership testing in commutative transformation semigroups ⋮ The complexity of intersecting finite automata having few final states ⋮ The parallel complexity of graph canonization under abelian group action ⋮ On the complexity of some problems on groups input as multiplication tables

Uses Software

• Cayley

Cites Work

• Unnamed Item
• Unnamed Item
• 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 Nielsen reduction and P-complete problems in free groups
• On the complexity of intersection and conjugacy problems in free groups
• Sylow's theorem in polynomial time
• A fast parallel algorithm to compute the rank of a matrix over an arbitrary field
• Towards a complexity theory of synchronous parallel computation
• Group-theoretic algorithms and graph isomorphism
• A polynomial bound for the orders of primitive solvable groups
• On the orders of primitive groups with restricted nonabelian composition factors
• Isomorphism of graphs of bounded valence can be tested in polynomial time
• The network complexity and the Turing machine complexity of finite functions
• Graphs and finite permutation groups
• A taxonomy of problems with fast parallel algorithms
• Polynomial-time algorithms for finding elements of prime order and sylow subgroups
• Polynomial-time versions of Sylow's theorem
• The Parallel Complexity of Abelian Permutation Group Problems
• Solvable and Nilpotent Subgroups of GL(n,q^m)
• An Algorithm for Finding the Blocks of a Permutation Group
• On Relating Time and Space to Size and Depth
• Fast parallel matrix and GCD computations

This page was built for publication: Parallel algorithms for solvable permutation groups