Using Multidimensional Matrices to Determine Graph Properties
Abstract
The need to determine the most appropriate data model increases, as the complexity of the designed computing systems and computer networks increases. The graph model is one of the main models for this kind of tasks. However, graphs are so complex for systems with many nodes, that heuristic methods, which are basic in graph theory, become too resource intensive. But it is possible to determine individual properties of graphs, as well as their parameters using the methods of the theory of multidimensional matrices, with significantly less computing power resources. This article discusses some properties of graphs that can be analyzed using the (λ,μ)-collapsed product of multidimensional matrices. The proofs of the correspondence of one of the numerical parameters of the vertices of the graph and the result of squaring the adjacency matrix of the graph are carried out. The parameters of the graph that do not affect its chromatic number are formulated, and an assumption is made about a possible relationship between the chromatic number and the number of odd cycles in the graph.
References
2. Munerman V.I., Munerman D.V. About the correspondence of data models and calculation models. Computer Mathematics Systems and Their Applications. 2021;(22):146-152. Available at: https://www.elibrary.ru/item.asp?id=46649891 (accessed 14.06.2022). (In Russ., abstract in Eng.)
3. Munerman V.I. Construction of hardware-software complexes architecture to improve massively data processing. Highly Available Systems. 2015;11(2):13-18. Available at: https://www.elibrary.ru/item.asp?id=23819273 (accessed 14.06.2022). (In Russ., abstract in Eng.)
4. Alam K.S., Shishir T.A., Azharul Hasan K.M. Efficient Partitioning Algorithm for Parallel Multidimensional Matrix Operations by Linearization. In: Senjyu T., Mahalle P.N., Perumal T., Joshi A. (eds.). Information and Communication Technology for Intelligent Systems. ICTIS 2020. Smart Innovation, Systems and Technologies. Vol. 195. Singapore: Springer; 2021. p. 141-149. doi: https://doi. org/10.1007/978-981-15-7078-0_13
5. Chen Y., Li K., Yang W., Xiao G., Xie X., Li T. Performance-Aware Model for Sparse Matrix-Matrix Multiplication on the Sunway TaihuLight Supercomputer. IEEE Transactions on Parallel and Distributed Systems. 2019;30(4):923-938. doi: https://doi. org/10.1109/TPDS.2018.2871189
6. Kwasniewski G., Kabić M., Besta M., VandeVondele J., Solcà R., Hoefler T. Red-blue pebbling revisited: near optimal parallel matrix-matrix multiplication. In: Proceedings of the International Conference for High Performance Computing, Networking, Storage and Analysis (SC'19). New York, NY, USA: Association for Computing Machinery; 2019. Article number: 24. p. 1-22. doi: https://doi.org/10.1145/3295500.3356181
7. Munerman V.I., Usachev V.V. [One way of parallel implementation of matrix multiplication]. Computer Mathematics Systems and Their Applications. 2013;(14):96-98. Available at: https://www.elibrary.ru/item.asp?id=20588350 (accessed 14.06.2022). (In Russ.)
8. Munerman V.I., Samoylova T.A. Parallel implementation for solving optimization problems by means of databases. Highly Available Systems. 2015;11(1):18-22. Available at: https://www.elibrary.ru/item.asp?id=23417734 (accessed 14.06.2022). (In Russ., abstract in Eng.)
9. Munerman V.I., Usachev V.V. [Parallel implementation of matrix multiplication using cloud computing in WINDOWS AZURE]. Computer Mathematics Systems and Their Applications. 2014;(15):97-98. Available at: https://www.elibrary.ru/item.asp?id=21947784 (accessed 14.06.2022). (In Russ.)
10. Munerman V.I., Zakharov V.N. [Parallel Algorithm for Multidimensional Matrix Multiplication]. Modern Information Technologies and IT-Education. 2015;11(2):384-390. Available at: https://www.elibrary.ru/item.asp?id=26167519 (accessed 14.06.2022). (In Russ.)
11. Munerman V.I., Samoylova T.A. Algebraic approach to algorithmization of routing problems. Highly Available Systems. 2018;14(5):50-56. (In Russ., abstract in Eng.) doi: https://doi.org/10.18127/j20729472-201805-08
12. Morozov S.A., Munerman V.I., Simakov V.A. Experimental analysis of multidimensional matrix approach to constructing routings in a graph. Proceedings of Universities. Electronics. 2022;27(5):676-686. (In Russ., abstract in Eng.) doi: https://doi.org/10.24151/1561-5405-2022-27-5-676-686
13. Kirsch R., Sibley C., Sprangel E. Graph universal cycles: Compression and connections to universal cycles. arXiv:2209.14198. 2022. 25 p. doi: https://doi.org/10.48550/arXiv.2209.14198
14. Xu J., Lu M., Liu K. Anti-Ramsey problems for cycles. Applied Mathematics and Computation. 2021;408:126345. doi: https://doi.org/10.1016/j.amc.2021.126345
15. Khoufi I., Laouiti A., Adjih C. A Survey of Recent Extended Variants of the Traveling Salesman and Vehicle Routing Problems for Unmanned Aerial Vehicles. Drones. 2019;3(3):66. doi: https://doi.org/10.3390/drones3030066
16. Hu Y., Yao Y., Lee W.S. A reinforcement learning approach for optimizing multiple traveling salesman problems over graphs. Knowledge-Based Systems. 2020;204:106244. doi: https://doi.org/10.1016/j.knosys.2020.106244
17. Xu X., Li J., Zhou M. Bi-Objective Colored Traveling Salesman Problems. IEEE Transactions on Intelligent Transportation Systems. 2022;23(7):6326-6336. doi: https://doi.org/10.1109/TITS.2021.3086625
18. Spivak S.I., Ismagilova A.S., Khamitova I.A. Graph-theoretical method for determining routes of complex chemical reactions. Doklady Physical Chemistry. 2010;434(2):169-171. doi: https://doi.org/10.1134/S0012501610100040
19. Emelchenkov E.P., Munerman V.I. One approach to analysis of high-availability systems. Highly Available Systems. 2018;14(5):36-41. (In Russ., abstract in Eng.) doi: https://doi.org/10.18127/j20729472-201805-05
20. Munerman V.I. [Multidimensional-matrix model of mass data processing]. Highly Available Systems. 2012;8(3):019-022. Available at: https://www.elibrary.ru/item.asp?id=18418156 (accessed 14.06.2022). (In Russ.)
21. Goncharov E.I. Multi-Dimensional Definition of Convolution. Modern Information Technologies and IT-Education. 2021;17(3):541-549. (In Russ., abstract in Eng.) doi: https://doi.org/10.25559/SITITO.17.202103.541-549
22. Moon J.W., Moser L. On cliques in graphs. Israel Journal of Mathematics. 1965;3(1):23-28. doi: https://doi.org/10.1007/BF02760024
23. König D. Graphok és mátrixok. Matematikai és Fizikai Lapok. 1931;38:116-119. Available at: http://real-j.mtak.hu/7307 (accessed 14.06.2022). (In Hungarian)
24. Karpov D.V., Gravin N.V. On Proper Colorings of Hypergraphs. Zapiski Nauchnykh Seminarov POMI. 2011;391(3):79-89. Available at: https://www.elibrary.ru/item.asp?id=17730707 (accessed 14.06.2022). (In Russ., abstract in Eng.)
25. Kupavskii A.B., Raigorodskii A.M. Distance graphs with large chromatic numbers and small clique numbers. Doklady Mathematics. 2012;85(3):394-398. doi: https://doi.org/10.1134/S1064562412030295
This work is licensed under a Creative Commons Attribution 4.0 International License.
Publication policy of the journal is based on traditional ethical principles of the Russian scientific periodicals and is built in terms of ethical norms of editors and publishers work stated in Code of Conduct and Best Practice Guidelines for Journal Editors and Code of Conduct for Journal Publishers, developed by the Committee on Publication Ethics (COPE). In the course of publishing editorial board of the journal is led by international rules for copyright protection, statutory regulations of the Russian Federation as well as international standards of publishing.
Authors publishing articles in this journal agree to the following: They retain copyright and grant the journal right of first publication of the work, which is automatically licensed under the Creative Commons Attribution License (CC BY license). Users can use, reuse and build upon the material published in this journal provided that such uses are fully attributed.
