UDK 519.6
A PARALLEL ALGORITHM FOR STUDY OF THE CAYLEY GRAPHS OF PERMUTATION GROUPS
A. А. Kuznetsov, A. S. Kuznetsova
Siberian State Aerospace University named after academician M. F. Reshetnev 31, Krasnoyarsky Rabochy Av., Krasnoyarsk, 660014, Russian Federation Е-mail: kuznetsov@sibsau.ru
An algorithm for computing the diameter, the average diameter and the growth function of the Cayley graph of a finite group given a fixed set of generators is presented. The correctness of the algorithm is proved. After that a parallel version of the algorithm for study of the Cayley graphs of permutation groups is presented. This algorithm can be useful in the design of the topology of a multiprocessor computing system (MCS). In this case the model of MCS will be presented as the Cayley graph in which the processors are the vertices of the graph and the edges correspond to physical connections between processors. Using of this algorithm allows us to study the characteristics of the Cayley graph to evaluate the performance of MCS.
the Cayley graph, a multiprocessor computing system.
References
- Holt D., Eick B., O'Brien E. Handbook of computational group theory. Boca Raton: Chapman & Hall/CRC Press, 2005. 514 p.
- Akers S., Krishnamurthy B. A group theoretic model for symmetric interconnection networks. Proceedings of the International Conference on Parallel Processing, 1986. P. 216–223.
- Schibell S., Stafford R. Processor interconnection networks and Cayley graphs. Discrete Applied Mathematics. 1992. Vol. 40. P. 337–357.
- Even S., Goldreich O. The Minimum Length Generator Sequence is NP-Hard. Journal of Algorithms. 1981. Vol. 2. P. 311–313.
- Kuznetsov A. A., Kuznetsova A. S. [Relation between growth functions in symmetric groups and tasks of combinatorial optimization]. Vestnik SibGAU, 2012, no. 6 (46), p. 93–97.
Kuznetsov Alexander Alexeevich – Doctor of Phisical and Mathematical Sciences, associate professor, Leading Researcher of Siberian State Aerospace University named after academician M.F. Reshetnev. E-mail: kuznetsov@sibsau.ru
Kuznetsova Alexandra Sergeevna – Research Scientist, Siberian State Aerospace University named after academician M.F. Reshetnev. E-mail: alexakulch@rambler.ru
