Parallel Algorithms for Permutation Groups and Graph Isomorphism
Eugene Luks
Committee:
Technical Report(May 1986)
Keywords:

We develop parallel techniques for dealing with permutation group problems. These are most effective on the class of groups with bounded non-abelian composition factors. For this class, we place in NC problems such as membership testing, finding the center and composition factors, and, of particular significance, finding pointwise-set-stabilizers. The last has applications to inĀ­stances of graph-isomorphism and we show that NC contains isomorphism-testing for vertex-colored graphs with bounded color multiplicity, a problem not long known to be in polynomial time.