Isomorphism of graphs of bounded valence can be tested in polynomial time
- 1 October 1980
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
Abstract
Suppose we are given a set of generators for a group G of permutations of a colored set A. The color automorphism problem for G involves finding generators for the subgroup of G which stabilizes the color classes. Testing isomorphism of graphs of valence ≤ t is polynomial-time reducible to the color automorphism problem for groups with small simple sections. The algorithm for the latter problem involves several divide-and-conquer tricks. The problem is solved sequentially on the G-orbits. An orbit is broken into a minimal set of blocks permuted by G. The hypothesis on G guarantees the existence of a 'large' subgroup P which acts as a p-group on the blocks. A similar process is repeated for each coset of P on G. Some results on primitive permutation groups are used to show that the algorithm runs in polynomial time.Keywords
This publication has 3 references indexed in Scilit:
- Polynomial-time algorithms for permutation groupsPublished by Institute of Electrical and Electronics Engineers (IEEE) ,1980
- An algorithm for finding the blocks of a permutation groupMathematics of Computation, 1975
- Endliche Gruppen IPublished by Springer Nature ,1967