A routing algorithm for the Cayley graphs generated by permutation groups

The purpose of this work is to create an effective routing algorithm on the Cayley graphs of permutation groups, superior in its characteristics to an algorithm using an automatic group structure. In the first section of the article we describe the auxiliary algorithm A–1 which allows numbering elements of a given permutation group. In the second section we present the algorithm A–2 for calculating the routing table on the Cayley graph and algorithm A–3 for determination the optimal route between two arbitrary vertices of the graph. Estimates of time and space complexity are also obtained for these algorithms. In the third section we describe the algorithm A–4 for calculation the minimal word of a group element. It is proved that the computational complexity of the algorithm will be proportional to the length of the input word. The fourth section presents the results of computer experiments for some groups of permutation groups, which compare the time for calculating the minimum words using algorithm A – 4 and an algorithm based on the construction of an automatic group structure. It is shown that A – 4 is much faster than its competitor.