Minimum bases for permutation groups: The greedy approximation

DOI10.1016/0196-6774(92)90020-DMaRDI QIDQ3990610zbMATH OpenFDO

Authors Kenneth D. Blaha

Publication date 28 June 1992

Published in Journal of Algorithms (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0196-6774(92)90020-D

zbMATH Keywords

\(NP\)-hardchain of stabilizersgreedy algorithmminimum basesnonredundant basespermutation groupsstrong generating set

Mathematics Subject Classification ID

Software, source code, etc. for problems pertaining to group theory (20-04) Series and lattices of subgroups (20D30) Generators, relations, and presentations of groups (20F05) Analysis of algorithms and problem complexity (68Q25)

Recommendations

• scientific article; zbMATH DE number 4165152
• Bases for primitive permutation groups and a conjecture of Babai
• scientific article; zbMATH DE number 3889771
• scientific article; zbMATH DE number 1273663
• scientific article; zbMATH DE number 475369

Cited in

(29)

• Linear optimization over permutation groups
• Permutation representations of loops.
• A proof of Pyber's base size conjecture
• Bases for permutation groups and matroids
• On relational complexity and base size of finite primitive groups
• Base sizes for primitive groups with soluble stabilisers
• Finding fixed point free elements and small bases in permutation groups
• The minimum length of a base for the symmetric group acting on partitions
• Computational group theory. Abstracts from the workshop held August 15--21, 2021 (hybrid meeting)
• The parameterized complexity of fixpoint free elements and bases in permutation groups
• scientific article; zbMATH DE number 3889771 (Why is no real title available?)
• scientific article; zbMATH DE number 4165152 (Why is no real title available?)
• scientific article; zbMATH DE number 4075066 (Why is no real title available?)
• ON THE HEIGHT AND RELATIONAL COMPLEXITY OF A FINITE PERMUTATION GROUP
• On the Saxl graph of a permutation group
• Algorithmic Problems for Metrics on Permutation Groups
• On the Burness-Giudici conjecture
• Minimal degree, base size, order: selected topics on primitive permutation groups
• Base sizes of primitive groups of diagonal type
• Independence and bases: theme and variations
• The base size of the symmetric group acting on subsets
• Symmetries, graph properties, and quantum speedups
• Irredundant bases for soluble groups
• Another character theoretic formula for base size
• Finite groups, fusion systems and applications. Abstracts from the workshop held March 16--21, 2025
• Greedy base sizes for sporadic simple groups
• A character theoretic formula for the base size
• Computing the order of a solvable permutation group
• Permutation codes

This page was built for publication: Minimum bases for permutation groups: The greedy approximation

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