Can I read A Random Base Change Algorithm for Permutation Groups on EtoBox?

A Random Base Change Algorithm for Permutation Groups by G. Cooperman; L. Finkelstein; N. Sarawagi is a scholarly article available to read on EtoBox.

What is A Random Base Change Algorithm for Permutation Groups about?

A new random base change algorithm is presented for a permutation group G acting on n points whose worst case asymptotic running time is better for groups with a small to moderate size base than any known deterministic algorithm.To achieve this time bound, the algorithm requires a random generator Rand(G) producing a random element of G with the uniform distribution and so that each call to Rand(G) takes time O(log(]G])n).The random base change algorithm has probability 1 -l/lG)2 of completing in time O(log2(IGJ)n) and outputting a data structure for representing the point stabilizer sequence relative to the new ordering which requires O(log(]G])n) space and which can be used to test group membership in time O(log(]G])n).Th e t ime to build a data structure for computing a Rand(G) with the above properties from a strong generatoring set for G is dominated by the time to construct the strong generating set from the original set of generators.

Author

G. Cooperman; L. Finkelstein; N. Sarawagi

Publisher

ACM

Published

1990

Language

EN