Heuristics for design of reliable telecommunication network

In this paper, the problem of finding a spanning $k$-tree of minimum weight in a complete weighted graph is considered. Such problem has a number of applications in designing reliable telecommunication networks. This problem is known to be NP-hard and generalizes a classical problem in graphs, the Minimum Spanning Tree Problem. For solving the problem, the following four effective heuristics are offered. The first heuristic is based on the idea of a well-known Prim's algorithm, the second one is based on a dynamic programming approach, and the other two use the idea of iterative improvement of a starting solution. Preliminary numerical experiment was performed to compare the effectiveness of the proposed algorithms with known heuristics and exact algorithms. Based on the results of the computational experiment, it follows that in order to solve such problem of small and medium dimension, it is advisable to use heuristics based on iterative improvement of a starting solution, and in order to solve the problem of high dimension it is advisable to use an algorithm based on dynamic programming approach, because it computes a solution with sufficient accuracy within reasonable computing time.