Научная электронная библиотека ULRICH'S Periodicals Directory

Сибирский государственный университет
науки и технологий имени академика М.Ф. Решетнева

Сибирский аэрокосмический журнал
ISSN 2712-8970 (Print) ISSN 2782-5760 (on-line)

Сведения об образовательной организации

UDK 519.6 Doi: 10.31772/2587-6066-2020-21-2-187-194
A ROUTING ALGORITHM FOR THE CAYLEY GRAPHS GENERATED BY PERMUTATION GROUPS
А. A. Kuznetsov, V. V. Kishkan
Reshetnev Siberian State University of Science and Technology; 31, Krasnoyarskii rabochii prospekt, Krasnoyarsk, 660037, Russian Federation
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.
Keywords: Cayley graph, a permutation group.
References

1.  Heydemann M. Cayley graphs and interconnection networks, in Graph symmetry: algebraic methods and applications (Editors: Hahnand Sabidussi). Dordrecht: Kluwer Academic Publishers. 1997, P. 167–226.

2.  Loz E. New record graphs in the degree-diameter problem. Australasian Journal of Combinatorics. 2008, Vol. 41, P. 63–80.

3.  Even S., Goldreich O. The Minimum Length Generator Sequence is NP–Hard. Journal of Algorithms. 1981, Vol. 2, P. 311–313.

4.  Holt D., Eick B., O'Brien E. Handbook of computational group theory. Boca Raton: Chapman & Hall/CRC Press, 2005, 514 p.

5.  Schibell S., Stafford R. Processor interconnection networks and Cayley graphs. Discrete Applied Mathematics. 1992, Vol. 40, P. 337–357.

6.  Stamoulis G., Tsitsiklis J. Effcient routing Scheme for Multiple Broadcasts in Hypercubes. IEEE Trans.
on Parallel and Distributed Systems. 1993, Vol. 4(7),
P. 725–739.

7.  Stamoulis G., Tsitsiklis J. The Effciency of Greedy Routing in Hypercubes and Butteries. IEEE Transaction on Communication. 1994, Vol. 42(11), P. 3051–3061.

8.  Kiasari A., Sarbazi-Azad H. Analytic performance comparison of hypercubes and star graphs with implementation constraints. Journal of Computer and System Sciences. 2008, No. 6, P. 1000–1012.

9.  Akers S., Krishnamurthy B. A group theoretic model for symmetric interconnection networks. Proceedings of the International Conference on Parallel Processing. 1986, P. 216–223.

10.  Tang K., Arden B. Vertex-transitivity and routing for Cayley graphs in GCR representations. Proceedings
of ACM Symposium on Applied Computing SAC. 1992,
P. 1180–1187.

11.  Wang L., Tang K. Topology-Based Routing for Xmesh in Wireless Sensor Networks. Lecture Notes in Electrical Engineering. 2009, Vol. 44, P. 229–239.

12.  Ryu J., Noel E., and Tang K. Fault-tolerant Routing on Borel Cayley Graph. IEEE ICC Next Generation Networking Symposium. 2012, P. 2872–2877.

13.  Shin J., Sirer E., Weatherspoon H., Kirovski D. On the feasibility of completely wireless datacenters. EEE/ACM Transaction On Networking. 2013, Vol. 21(5), P. 1666–1679.

14.  Epstein D., Paterson M., Cannon J., Holt D., Levy S. and Thurston W. Word Processing in Groups. Boston: Jones and Barlett Publishers, 1992, 330 p.

15.  Camelo M., Papadimitriou D., Fabrega L., Vila P. Efficient Routing in DataCenter with Underlying Cayley Graph. Proceedings of the 5th Workshop on Complex Networks CompleNet. 2014, P. 189–197.

16.  Knuth D. The Art of Computer Programming, Volume 4A: Combinatorial Algorithms, Part 1. Boston: Addison-Wesley Professional, 2011, 912 p.

17.  Sims C. Computational methods in the study of permutation groups, Computational problems in abstract algebra (Pergamon Press, Oxford). 1970, P.169–183.

18.  Seress A. Permutation Group Algorithms. Cambridge: Cambridge University Press, 2003, 274 p.

19.  Skiena S. The Algorithm Design Manual. London: Springer Science+Business Media, 2008, 730 p.


Kuznetsov Alexander Alexeevich – D. Sc., Professor, Head of Institute of Space Research and High Technologies;
Reshetnev Siberian State University of Science and Technology. E-mail: alex_kuznetsov80@mail.ru.
Kishkan Vladimir Vladimirovich – Postgraduate student; Reshetnev Siberian State University of Science and
Technology. E-mail: kishkan@mail.ru.  


  A ROUTING ALGORITHM FOR THE CAYLEY GRAPHS GENERATED BY PERMUTATION GROUPS