Building communication networks: on the application of the Kruskal’s algorithm in the problems of large dimensions

Boris Melnikov, Yulia Terentyeva

Abstract


The paper deals with the development of the topology of ultra-large communication networks, i.e. networks containing several thousand vertices. In this case, the coordinates of the vertices of the undirected graph are somehow predetermined and a set of edges must be constructed. The main point of the options we are considering for developing the network topology is the minimum of the sum of weights of the edges; however, we note in advance that this criterion of minimality is often not the only objective function in the practical problems we are considering. In our previous papers, two realistically considered tasks were formulated. However, everything is not so simple, and we cannot use the direct version of Kruskal’s algorithm. The complexity of this algorithm  depends on the representation of the data, i.e. the data structures used. In our situation (when the number of considered vertices is approximately 5000 to 10000), the operation of a simple version of the algorithm takes about a half an hour, which, of course, is acceptable for a one-time solution to the problem under consideration, but it is unacceptable in the case when such solutions are constructed repeatedly (in particular, iteratively). Some temporary improvements to the practical operation of the algorithm provide different options for using complex data structures. For example, we can somehow store a certain number of unused edges of small length, and, if necessary, sort these edges, add new ones to them, etc. However, this approach is not a “panacea”, since in the worst case the complexity estimates (and the running time of the algorithms) are the same. All this formulates the need to consider and implement heuristic algorithms, instead of exact, exhaustive ones. The subject of this paper can be formulated as follows. We are moving from exact algorithms (in particular, Kruskal’s algorithm) to some heuristics. Moreover, for the starting problem that we are considering, we cannot work without heuristic algorithm at all. However, we describe two specific variants of a simple implementation of Kruskal’s algorithm for problems of large dimensions. We also formulated two heuristics and two corresponding algorithms. In our opinion, one of these algorithms turned out to be quite acceptable; we present some practical results of computational experiments. And it is very important that these two heuristics will be useful not only for such “initial problem”, but also for much more complex problems

Full Text:

PDF (Russian)

References


Melnikov B., Meshchanin V, Terentyeva Y. Implementation of optimality criteria in the design of communication networks // Journal of Physics: Conference Series, International Scientific Conference ICMSIT–2020: Metrological Support of Innovative Technological, ICMSIT2020 (paper 3095), http://conf.domnit.ru/en/conferences/icmsit-2020-en/.

Bulynin A., Melnikov B., Meshchanin V, Terentyeva Y. Optimization problems arising in the design of highdimensional communication networks, and some heuristic methods for their solution //Informatization and Communication. – 2020. – No. 1. – P. 34–40, https://elibrary.ru/item.asp?id=42839357 (in Russian).

Bulynin A., Melnikov B., Meshchanin V, Terentyeva Y. Communication network design algorithms using various types of greedy heuristics // Information technologies and nanotechnologies (ITNT-2020). Proceedings of the VI International Conference and Youth School. – 2020. – P. 856–860, https://www.elibrary.ru/item.asp?id=43576630 (in Russian).

Kruskal J. On the shortest spanning subtree of a graph and the traveling salesman problem // Proceedings of the American Mathematical Society. – 1956. – Vol. 7, No. 1. – P. 48–50, doi: 10.1090/S0002-9939-1956-0078686-7.

Cormen T., Leiserson C., Rivest R, Stein C. Introduction to Algorithms, Second Edition // Massachusetts: MIT Press and McGraw-Hill, 2001, ISBN 0-262-03293-7.

Goodrich M., Tamassia R. Data Structures and Algorithms in Java, Fourth Edition // NJ: John Wiley & Sons, Inc., 2006, ISBN 0-471-73884-0.

Prim R. Shortest connection networks and some generalizations // Bell System Technical Journal. – 1957. – Vol. 36, No. 6. – P. 1389–1401, doi: 10.1002/j.1538-7305.1957.tb01515.

S. Russell S., Norvig P. Artificial Intelligence: A Modern Approach // NJ: Simon & Schuster, 1995, ISBN 978-0-13-103805-9.

Melnikov B. Discrete optimization problems – some new heuristic approaches // Proceedings – Eighth International Conference on High-Performance Computing in Asia-Pacific Region, HPC Asia 2005, Beijing, 2005. – P. 73–80. doi: 10.1109/HPCASIA.2005.34.

Melnikov B., Radionov A, Moseev A, Melnikova E. Some specific heuristics for situation clustering problems //Proceedings – 1st International Conference on Software and Data Technologies, ICSOFT 2006, Setubal, 2006. – P. 272–279. doi: 10.5220/0001317002720279 .

Makarkin S., Melnikov B., Trenina M. An approach to solving the pseudo-geometric version of the traveling salesman problem // News of higher educational institutions. Volga region. Physical and mathematical Sciences. – 2015. – No. 2 (34). – P. 135–147. https://elibrary.ru/item.asp?id=24254294 (in Russian).

Melnikov B., Pivneva S., Trifonov M. Multi-heuristic approach to comparing the quality of defined metrics on a set of DNA sequences // Modern Information Technologies and IT Education. – 2017. – Vol. 13, No 2. – P. 89–96. https://elibrary.ru/item.asp?id=30258646 (in Russian).

Melnikov B., Romanov N. Once again on the heuristics for the traveling salesman problem // Theoretical problems of computer science and its applications. – 2001. – Vol. 4. – P. 81–88. https://www.elibrary.ru/ title_about.asp?id=38720 (in Russian).

Makarkin S., Melnikov B. Geometric methods for solving the pseudo-geometric version of the traveling salesman problem // Stochastic Optimization in Computer Science. – 2013. – Vol. 9, No 2. – P. 54–72. https://www.elibrary.ru/item.asp?id=20960443 (in Russian).

Melnikov B., Radionov A. A choice of strategy in nondeterministic antagonistic games // Programming and Computer Software. – 1998. – Vol. 24, No. 5. – С. 247–252. https://elibrary.ru/item.asp?id=13280793.

Melnikov B., Melnikova E., Pivneva S., Churikova N., Dudnikov V, Prus M. Multi-heuristic and game approaches in search problems of the graph theory // Proceedings of the ITNT-2018. Samara National Research University named after academician S. P. Korolev. – 2018. – P. 2884–2892. https://elibrary.ru/item.asp?id=34895071, http://repo.ssau.ru/bitstream/Informacionnye-tehnologii-i-nanotehnologii/Multiheuristic-and-game-approachesin-search-problems-of-the-graph-theory69142/1/paper_389.pdf.

Melnikov B., Trenina M. On a problem of reconstructing distance matrices between DNA chains // International Journal of Open Information Technologies. – 2018. – Vol. 6, No. 6. – P. 1–13. http://injoit.org/index.php/j1/article/view/571/562 (in Russian).

Melnikov B., Trenina M., Melnikova E. Different Approaches to Solving the Problem of Reconstructing the Distance Matrix Between DNA Chains // Communications in Computer and Information Science, 1201 CCIS. – 2020. – P. 211–223. https://link.springer.com/chapter/10.1007/978-3-030-46895-8_17.

Lagutin M. Visual mathematical statistics // Moscow: BINOM. Knowledge lab, 2015. ISBN 978-5-9963-2955-7 (in Russian).

Melnikov B., Zubova T. Mathematical modeling of organization management by value guidelines: algorithms for complex estimation and selection of pseudo-optimal actions // International Journal of Open Information Technologies. – 2018. – Vol. 6, No. 3. – P. 1–8. http://injoit.org/index.php/j1/article/view/545/518 (in Russian).

Zubova T., Melnikov B., Soldatov A. Mathematical modeling of organization management by value guidelines: algorithms for analytic hierarchy process on the basis of quantitative significance criteria // International Journal of Open Information Technologies. – 2019. – Vol. 7, No. 8. – P. 1–8. http://injoit.org/index.php/j1/article/view/738/746 (in Russian).

Terentyeva Y. A method for estimating the reliability of a large-scale communication network based on dependent paths // Informatization and Communication. – 2017. – No. 1. – P. 122–128, https://www.elibrary.ru/item.asp?id=29076288 (in Russian).


Refbacks

  • There are currently no refbacks.


Abava  Absolutech Convergent 2020

ISSN: 2307-8162