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

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

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

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

UDK 519.6
USING HIGH-PERFORMANCE COMPUTATIONS FOR STUDYING MODIFIED BUBBLE-SORT GRAPHS
А. A. Kuznetsov*, V. V. Kishkan
Reshetnev Siberian State University of Science and Technology 31, Krasnoyarsky Rabochy Av., Krasnoyarsk, 660037, Russian Federation *Е-mail: kuznetsov@sibsau.ru
The definition of the Cayley graph was given by the famous English mathematician Arthur Cayley in the XIX century to represent algebraic group defined by a fixed set of generating elements. At present, Cayley graphs are widely used both in mathematics and in applications. In particular, these graphs are used to represent computer networks, including the modeling of topologies of multiprocessor computer systems – supercomputers. This is due to the fact that Cayley graphs have many attractive properties such as regularity, vertex transitive, small diameter and degree at a sufficiently large number of vertices in the graph. For example, such a basic network topology as the “ring”, “hypercube” and “torus” are the Cayley graphs. Using supercomputer computations we obtained the previously unknown characteristics of modified bubble-sort Cayley graphs of dimensions 14 and 15.
Keywords: the Cayley graph, a multiprocessor computing system, a modified bubble-sort graph.
References

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

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

3. Cooperman G., Finkelstein L. New methods for using Cayley graphs in interconnection networks. Discrete Applied Mathematics. 1992, Vol. 37, P. 95–118.

4. Lakshmivarahan S., Jho J., Dhall S. Symmetry in interconnection networks based on Cayley graphs of permutation groups: A survey. Parallel Computing. 1993, Vol. 19, P. 361–407.

5. Heydemann M. Cayley graphs and interconnection networks, in Graph symmetry: algebraic methods and applications. Dordrecht: Kluwer Academic Publishers. 1997, P. 167–226.

6. Xu J. Topological Structure and Analysis of Interconnection Networks. Dordrecht: Kluwer Academic Publishers, 2001, 352 p.

7. Parhami B. Swapped interconnection networks: Topological, performance, and robustness attributes. Journal of Parallel and Distributed Computing. 2005, Vol. 65, P. 1443–1452.

8. Asai S., Kounoike, Shinano Y., Kaneko K. Computing the diameter of 17–pancake graphs using a PC cluster. LNSC. 2006, Vol. 4128, P. 1114–1124.

9. Chen B., Xiao W., Parhami B. Internode distance and optimal routing in a class of alternating group networks. IEEE Transactionson Computers. 2006, Vol. 55, P. 1645–1648.

10. Wang L., Tang K. The Cayley Graph implementation in TinyOS for dense wireless sensor networks. Proc. of the 6th Wireless Telecommunications Symposium, 2007.

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

12. Kuznetsov A. A., Kuznetsova A. S. [A parallel algorithm for study of the Cayley graphs of permutation groups]. Vestnik SibGAU. 2014, No. 1(53), P. 34–39 (In Russ.).

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

14. Kuznetsov A. A., Kuznetsova A. S. [Relation between growth functions insymmetric groups and tasks of combinatorial optimization]. Vestnik SibGAU. 2012, No. 6(46), P. 93–97 (In Russ.).

15. Kuznetsov A. A. [An algorithm of computation of the growth functions in finite two-generated groups of exponent five]. Prikladnaya Diskretnaya Matematika, 2016, No. 3(33), P. 116–125 (In Russ.).


Kuznetsov Alexander Alexeevich – Dr. Sc., Professor, Head of Institute of Space Research and High

Technologies, Reshetnev Siberian State University of Science and Technology. E-mail: kuznetsov@sibsau.ru.

Kishkan Vladimir Vladimirovich – postgraduate student, Reshetnev Siberian State University of Science and

Technology. E-mail: kishkan@mail.ru.