Pruning minimum spanning trees and cutting longest edges to connect a given number of nodes by minimizing total edge length
Вантажиться...
Дата
2023
Автори
Науковий керівник
Назва журналу
Номер ISSN
Назва тому
Видавець
National Technical University of Ukraine "Igor Sikorsky Kyiv Polytechnic Institute"
Анотація
Background. Whereas in many tasks of designing efficient telecommunication networks, the number of network nodes is limited, the initial choice of nodes is wider. There are more possible locations than factually active tools to be settled to those locations to further satisfy consumers. This induces an available node constraint problem. Objective. Given an initial set of planar nodes, the problem is to build a minimum spanning tree connecting a given number of the nodes, which is less than the cardinality of the initial set. Therefore, the available node constraint problem aims at building an optimally minimum spanning tree to connect a given number of planar nodes being less than an initial number of nodes by minimizing the tree length. Methods. The initial set of nodes is triangulated. This gives a set of edges, whose lengths are calculated and used as graph weights. A minimum spanning tree is built over this graph. The desired number of nodes is reached by pruning the minimum spanning tree connecting the initial number of nodes, where free edges whose weights are the largest are iteratively removed from the tree. The other approach, the cutting method, removes longest edges off the initial minimum spanning tree, regardless of whether they are free or not. Results. Unlike the pruning method, the method of cutting longest edges may result in a minimum spanning tree connecting fewer nodes than the desired number. However, the cutting method often outputs a shorter tree, especially when the edge length varies much. Besides, the cutting method is slower due to it iteratively rebuilds a minimum spanning tree. Conclusions. The problem is initially solved by the pruning method. Then the cutting method is used and its solution is compared to the solution by the pruning method. The best tree is shorter. A tradeoff for the nodes and tree length is possible.
Опис
Ключові слова
minimum spanning tree, triangulation, edge lengths, pruning the tree, cutting longest edges, мінімальне сполучне дерево, триангуляція, довжини ребер, підрізання дерева, відрізання найдовших ребер
Бібліографічний опис
Romanuke, V. Pruning minimum spanning trees and cutting longest edges to connect a given number of nodes by minimizing total edge length / Romanuke Vadim V. // Information and telecommunication sciences : international research journal. – 2023. – Vol. 14, N. 2. – Pp. 40-52. – Bibliogr.: 21 ref.