Pruning minimum spanning trees and cutting longest edges to connect a given number of nodes by minimizing total edge length

Скорочена інформація про документ
dc.contributor.authorRomanuke, Vadim V.
dc.date.accessioned2024-02-29T08:27:34Z
dc.date.available2024-02-29T08:27:34Z
dc.date.issued2023
dc.description.abstractBackground. 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.
dc.description.abstractotherПроблематика. У багатьох завданнях проєктування ефективних телекомунікаційних мереж кількість вузлів мережі є обмеженою, але вибір вузлів є ширшим. Для подальшого задоволення споживачів фактично існує більше потенційних місць розташування, ніж наявних засобів для їх розміщення у цих місцях. Це призводить до виникнення задачі з обмеженням доступних вузлів. Мета дослідження. Для даної початкової множини вузлів на площині задача полягає у побудові мінімального сполучного дерева, що поєднує задану кількість вузлів, котра є меншою за кількість елементів початкової множини. Тому задача з обмеженням доступних вузлів має на меті побудову оптимально мінімального сполучного дерева для сполучення заданого числа вузлів на площині, що є меншим за початкове число вузлів, за мінімізації довжини цього дерева. Методика реалізації. Виконується триангуляція початкової множини вузлів. Це дає набір ребер, чиї довжини обчислюються і використовуються як ваги графа. На цьому графі будується мінімальне сполучне дерево. Бажана кількість вузлів досягається підрізанням цього мінімального сполучного дерева, з якого ітеративно видаляються вільні ребра, чиї ваги є найбільшими. Інший підхід, метод відрізання, видаляє найдовші ребра з початкового мінімального сполучного дерева незалежно від того, чи вони є вільними. Результати дослідження. На відміну від методу підрізання, метод відрізання найдовших ребер може призвести до мінімального сполучного дерева, що поєднуватиме менше вузлів, ніж потрібно. Однак метод відрізання часто видає коротше дерево, особливо коли довжина ребра сильно варіюється. Крім того, метод відрізання є повільнішим через те, що він ітеративно перебудовує мінімальне сполучне дерево. Висновки. Спочатку задача розв’язується методом підрізання. Тоді застосовується метод відрізання і його розв’язок порівнюється з розв’язком за методом підрізання. Коротше дерево є найкращим. Можливий компроміс числа вузлів і довжини дерева.
dc.format.pagerangePp. 40-52
dc.identifier.citationRomanuke, 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.
dc.identifier.doihttps://doi.org/10.20535/2411-2976.22023.40-52
dc.identifier.orcid0000-0001-9638-9572
dc.identifier.urihttps://ela.kpi.ua/handle/123456789/65081
dc.language.isoen
dc.publisherNational Technical University of Ukraine "Igor Sikorsky Kyiv Polytechnic Institute"
dc.publisher.placeKyiv
dc.relation.ispartofInformation and telecommunication sciences: international research journal, Vol. 14, N. 2
dc.rights.urihttps://creativecommons.org/licenses/by/4.0/
dc.subjectminimum spanning tree
dc.subjecttriangulation
dc.subjectedge lengths
dc.subjectpruning the tree
dc.subjectcutting longest edges
dc.subjectмінімальне сполучне дерево
dc.subjectтриангуляція
dc.subjectдовжини ребер
dc.subjectпідрізання дерева
dc.subjectвідрізання найдовших ребер
dc.subject.udc519.172.1+004.722.25
dc.titlePruning minimum spanning trees and cutting longest edges to connect a given number of nodes by minimizing total edge length
dc.title.alternativeПідрізання мінімальних сполучних дерев та відрізання найдовших ребер для сполучення даної кількості вузлів при мінімізації загальної довжини ребер
dc.typeArticle

Файли

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

Зібрання

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