2023

Постійне посилання на фонд

https://ela.kpi.ua/handle/123456789/58198

Переглянути

Перегляд 2023 за Автор "Romanuke, Vadim V."

Зараз показуємо 1 - 2 з 2
  • Ескіз
    ДокументВідкритий доступ
    Building minimum spanning trees by limited number of nodes over triangulated set of initial nodes
    (National Technical University of Ukraine "Igor Sikorsky Kyiv Polytechnic Institute", 2023) Romanuke, Vadim V.
    Background. The common purpose of modeling and using minimum spanning trees is to ensure efficient coverage. In many tasks of designing efficient telecommunication networks, the number of network nodes is usually limited. In terms of rational allocation, there are more possible locations than factually active tools to be settled to those locations. 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 can be less than the cardinality of the initial set. The root node is primarily assigned, but it can be changed if needed. Methods. To obtain a set of edges, a Delaunay triangulation is performed over the initial set of nodes. Distances between every pair of the nodes in respective edges are calculated. These distances being the lengths of the respective edges are used as graph weights, and a minimum spanning tree is built over this graph. Results. The problem always has a solution if the desired number of nodes (the number of available recipient nodes) is equal to the number of initially given nodes. If the desired number is lesser, the maximal edge length is found and the edges of the maximal length are excluded while the number of minimum spanning tree nodes is greater than the desired number of nodes. Conclusions. To build a minimum spanning tree by a limited number of nodes, it is suggested using the Delaunay triangulation and an iterative procedure in order to meet the desired number of nodes. Planar nodes of an initial set are triangulated, whereupon the edge lengths are used as weights of a graph. The iterations to reduce nodes are done only if there are redundant nodes. When failed, the root node must be changed before the desired number of nodes is changed.
  • Ескіз
    ДокументВідкритий доступ
    Pruning minimum spanning trees and cutting longest edges to connect a given number of nodes by minimizing total edge length
    (National Technical University of Ukraine "Igor Sikorsky Kyiv Polytechnic Institute", 2023) Romanuke, Vadim V.
    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.