Building minimum spanning trees by limited number of nodes over triangulated set of initial nodes

Скорочена інформація про документ
dc.contributor.authorRomanuke, Vadim V.
dc.date.accessioned2023-07-18T12:06:56Z
dc.date.available2023-07-18T12:06:56Z
dc.date.issued2023
dc.description.abstractBackground. 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.uk
dc.description.abstractotherПроблематика. Загальна мета моделювання та використання мінімальних сполучних дерев полягає у забезпеченні ефективного покриття. У багатьох завданнях проєктування ефективних телекомунікаційних мереж кількість вузлів мережі зазвичай є обмеженою. У термінах раціонального розміщення це означає, що фактично існує більше потенційних місць розташування, ніж наявних засобів для їх розміщення у цих місцях. Мета дослідження. Для даної початкової множини вузлів на площині задача полягає у побудові мінімального сполучного дерева, що поєднує задану кількість вузлів, котра може бути меншою за кількість елементів початкової множини. Кореневий вузол першопочатково задається, однак за необхідності він може бути змінений. Методика реалізації. Для отримання множини ребер виконується триангуляція Делоне на початковій множині вузлів. Обчислюються відстані між кожною парою вузлів у відповідних ребрах. Ці відстані, котрі є довжинами відповідних ребер, використовуються як ваги для графа, і на цьому графі будується мінімальне сполучне дерево. Результати дослідження. Дана задача завжди має розв’язок за умови, якщо бажана кількість вузлів (кількість доступних вузлів-приймачів) рівна кількості початково даних вузлів. Якщо бажана кількість є меншою, знаходиться максимальна довжина ребра, й усі ребра максимальної довжини виключаються доки кількість вузлів мінімального сполучного дерева є більшою за бажану кількість вузлів. Висновки. Для побудови мінімального сполучного дерева за обмеженої кількості вузлів запропоновано використовувати триангуляцію Делоне та ітеративну процедуру задля досягнення бажаної кількості вузлів. Виконується триангуляція вузлів з початкової множини на площині, після чого довжини ребер використовуються як ваги графа. Ітерації задля скорочення вузлів виконуються лише за наявності зайвих вузлів. У випадку відсутності розв’язку мусить бути змінений кореневий вузол перед тим, як змінювати бажану кількість вузлів.uk
dc.format.pagerangePp. 41-40uk
dc.identifier.citationRomanuke, V. Building minimum spanning trees by limited number of nodes over triangulated set of initial nodes / Romanuke Vadim V. // Information and telecommunication sciences : international research journal. – 2023. – Vol. 14, N. 1. – Pp. 41-50. – Bibliogr.: 18 ref.uk
dc.identifier.doihttps://doi.org/10.20535/2411-2976.12023.41-50
dc.identifier.orcid0000-0001-9638-9572uk
dc.identifier.urihttps://ela.kpi.ua/handle/123456789/58237
dc.language.isoenuk
dc.publisherNational Technical University of Ukraine "Igor Sikorsky Kyiv Polytechnic Institute"uk
dc.publisher.placeKyivuk
dc.relation.ispartofInformation and telecommunication sciences: international research journal, Vol. 14, N. 1uk
dc.rights.urihttps://creativecommons.org/licenses/by/4.0/
dc.subjectminimum spanning treeuk
dc.subjecttriangulationuk
dc.subjectedge lengthsuk
dc.subjectredundant nodesuk
dc.subjectroot nodeuk
dc.subjectмінімальне сполучне деревоuk
dc.subjectтриангуляціяuk
dc.subjectдовжини реберuk
dc.subjectзайві вузлиuk
dc.subjectкореневий вузолuk
dc.subject.udc519.172.1+004.722.25uk
dc.titleBuilding minimum spanning trees by limited number of nodes over triangulated set of initial nodesuk
dc.title.alternativeПобудова мінімальних сполучних дерев за обмеженої кількості вузлів на триангульованій множині початкових вузлівuk
dc.typeArticleuk

Файли

Контейнер файлів
Зараз показуємо 1 - 1 з 1
Ескіз
Назва:
282075-650861-1-10-20230619.pdf
Розмір:
773.31 KB
Формат:
Adobe Portable Document Format
Опис:
Завантажити
Ліцензійна угода
Зараз показуємо 1 - 1 з 1
Ескіз недоступний
Назва:
license.txt
Розмір:
9.1 KB
Формат:
Item-specific license agreed upon to submission
Опис:
Завантажити

Зібрання

Information and telecommunication sciences: international research journal, Vol. 14, N. 1