Treffer: A parallelization of Miller's nlog n isomorphism technique: A parallelization of Miller's \(n^{\log n}\) isomorphism technique

The authors first present G. L. Miller's sequential algorithm of complexity \(O(n^{\log n+c})\) for isomorphism testing of Steiner triple systems of order \(n\), \(\text{STS}(n)\), as Algorithm Canonical, a recursive procedure returning a canonical form of an \(\text{STS}(n)\). Two main steps in the algorithm have been called forcing and choosing and the forcing step is shown as the computation of a closure of a set defined in a suitable way needing at most \(3\log n\) iterations. The algorithm is then parallelized using a CREW-PRAM model needing \(O(n^{\log n+2})\) processors and a total running time of \(O((\log n)^ 2)\). Whether the problem lies in NC is left open. It is also shown that both the sequential and parallel algorithms can be generalized to compute canonical forms of quasi-semigroups.