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

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