Parallel algorithms for permutation groups and graph isomorphism
- 1 October 1986
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- No. 02725428,p. 292-302
- https://doi.org/10.1109/sfcs.1986.39
Abstract
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-stabilisers. The last has applications to instances 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.Keywords
This publication has 20 references indexed in Scilit:
- A simple parallel algorithm for the maximal independent set problemPublished by Association for Computing Machinery (ACM) ,1985
- A fast parallel algorithm for the maximal independent set problemPublished by Association for Computing Machinery (ACM) ,1984
- Computational complexity and the classification of finite simple groupsPublished by Institute of Electrical and Electronics Engineers (IEEE) ,1983
- Normal forms for trivalent graphs and graphs of bounded valencePublished by Association for Computing Machinery (ACM) ,1983
- On the orders of primitive groups with restricted nonabelian composition factorsJournal of Algebra, 1982
- Isomorphism of graphs of bounded valence can be tested in polynomial timeJournal of Computer and System Sciences, 1982
- Isomorphism of graphs with bounded eigenvalue multiplicityPublished by Association for Computing Machinery (ACM) ,1982
- Polynomial-time algorithms for permutation groupsPublished by Institute of Electrical and Electronics Engineers (IEEE) ,1980
- On simultaneous resource boundsPublished by Institute of Electrical and Electronics Engineers (IEEE) ,1979
- Fast Parallel Matrix Inversion AlgorithmsSIAM Journal on Computing, 1976