A method for sorting of spanning trees
In this article the author suggests a method for sorting of spanning tree graphs. Spanning trees are widely used in various areas, including combinatorics, chemistry, electrodynamics, and logistics. In decision theory spanning trees provide a handy tool for capturing of all the information from expe...
Збережено в:
| Дата: | 2026 |
|---|---|
| Автор: | |
| Формат: | Стаття |
| Мова: | Українська |
| Опубліковано: |
Інститут проблем реєстрації інформації НАН України
2026
|
| Теми: | |
| Онлайн доступ: | https://drsp.ipri.kiev.ua/article/view/358849 |
| Теги: |
Додати тег
Немає тегів, Будьте першим, хто поставить тег для цього запису!
|
| Назва журналу: | Data Recording, Storage & Processing |
Репозитарії
Data Recording, Storage & Processing| _version_ | 1865395318701424640 |
|---|---|
| author | Каденко, С. В. |
| author_facet | Каденко, С. В. |
| author_sort | Каденко, С. В. |
| baseUrl_str | http://drsp.ipri.kiev.ua/oai |
| collection | OJS |
| datestamp_date | 2026-05-16T22:01:18Z |
| description | In this article the author suggests a method for sorting of spanning tree graphs. Spanning trees are widely used in various areas, including combinatorics, chemistry, electrodynamics, and logistics. In decision theory spanning trees provide a handy tool for capturing of all the information from expert estimates, provided in the form of pair-wise comparisons of alternatives. On the one hand, combinatorial method of spanning tree enumeration allows us to exploit the redundancy of expert information most thoroughly. On the other, it is characterized by high computational complexity, especially when the number of compared alternatives is larger than 7. Moreover, if multiple experts need to compare several sets of alternatives, then the task of processing the results of expert sessions and deriving priorities from all pair-wise comparison matrices becomes extremely labor-intensive. Therefore, it makes sense to define which basic pair-wise comparison sets tend to be more consistent, i.e. which spanning trees represent preference structures that are more resilient to expert errors. Having analyzed recent research on the subject, the author argues that spanning trees with smaller diameters correspond to preference structures which are more stable against errors made by experts during pair-wise comparisons of alternatives. Spanning tree graphs, in their turn, are easily represented by the so-called Prüfer codes. It is shown that spanning tree diameter depends on the number of repetitions of node numbers in these codes. This property provides the basis for the original spanning tree enumerations method. If, due to large number of compared alternatives, all spanning trees cannot be enumerated, then it makes sense to focus on trees with smaller diameters in the first place. This approach allows us to reduce the computational complexity of combinatorial spanning tree enumeration method without significant loss of information. The study confirms the main outcomes of previous research on the subject. It is illustrated by numeric examples which speak in favor of the method’s efficiency. Tabl.: 1. Fig.: 3. Refs: 20 titles. |
| doi_str_mv | 10.35681/1560-9189.2026.28.1.358849 |
| first_indexed | 2026-05-17T01:00:05Z |
| format | Article |
| id | drspiprikievua-article-358849 |
| institution | Data Recording, Storage & Processing |
| keywords_txt_mv | keywords |
| language | Ukrainian |
| last_indexed | 2026-05-17T01:00:05Z |
| publishDate | 2026 |
| publisher | Інститут проблем реєстрації інформації НАН України |
| record_format | ojs |
| spelling | drspiprikievua-article-3588492026-05-16T22:01:18Z A method for sorting of spanning trees Метод сортування покривних дерев Каденко, С. В. експертне оцінювання, матриця парних порівнянь, покривне дерево, діаметр графа, код Прюфера expert estimation, pair-wise comparison matrix, spanning tree, graph diameter, Prüfer code In this article the author suggests a method for sorting of spanning tree graphs. Spanning trees are widely used in various areas, including combinatorics, chemistry, electrodynamics, and logistics. In decision theory spanning trees provide a handy tool for capturing of all the information from expert estimates, provided in the form of pair-wise comparisons of alternatives. On the one hand, combinatorial method of spanning tree enumeration allows us to exploit the redundancy of expert information most thoroughly. On the other, it is characterized by high computational complexity, especially when the number of compared alternatives is larger than 7. Moreover, if multiple experts need to compare several sets of alternatives, then the task of processing the results of expert sessions and deriving priorities from all pair-wise comparison matrices becomes extremely labor-intensive. Therefore, it makes sense to define which basic pair-wise comparison sets tend to be more consistent, i.e. which spanning trees represent preference structures that are more resilient to expert errors. Having analyzed recent research on the subject, the author argues that spanning trees with smaller diameters correspond to preference structures which are more stable against errors made by experts during pair-wise comparisons of alternatives. Spanning tree graphs, in their turn, are easily represented by the so-called Prüfer codes. It is shown that spanning tree diameter depends on the number of repetitions of node numbers in these codes. This property provides the basis for the original spanning tree enumerations method. If, due to large number of compared alternatives, all spanning trees cannot be enumerated, then it makes sense to focus on trees with smaller diameters in the first place. This approach allows us to reduce the computational complexity of combinatorial spanning tree enumeration method without significant loss of information. The study confirms the main outcomes of previous research on the subject. It is illustrated by numeric examples which speak in favor of the method’s efficiency. Tabl.: 1. Fig.: 3. Refs: 20 titles. Статтю присвячено розробці методу сортування покривних дерев за діаметром. Покривні дерева широко застосовуються в теорії підтримки прийняття рішень, зокрема для отримання найбільш повної інформації з матриць експертних парних порівнянь. Метод дозволяє, за необхідності, без суттєвої втрати інформації знизити трудомісткість комбінаторного перебору базисних множин парних порівнянь під час обчислення відносних ваг альтернатив. Запропонований метод базується на певних когнітивних особливостях процесу експертного оцінювання множини альтернатив і використовує бієктивну відповідність між покривними деревами та кодами Прюфера. Інститут проблем реєстрації інформації НАН України 2026-03-17 Article Article application/pdf https://drsp.ipri.kiev.ua/article/view/358849 10.35681/1560-9189.2026.28.1.358849 Data Recording, Storage & Processing; Vol. 28 No. 1 (2026); 129-136 Регистрация, хранение и обработка данных; Том 28 № 1 (2026); 129-136 Реєстрація, зберігання і обробка даних; Том 28 № 1 (2026); 129-136 1560-9189 uk https://drsp.ipri.kiev.ua/article/view/358849/346657 Авторське право (c) 2026 Реєстрація, зберігання і обробка даних |
| spellingShingle | expert estimation pair-wise comparison matrix spanning tree graph diameter Prüfer code Каденко, С. В. A method for sorting of spanning trees |
| title | A method for sorting of spanning trees |
| title_alt | Метод сортування покривних дерев |
| title_full | A method for sorting of spanning trees |
| title_fullStr | A method for sorting of spanning trees |
| title_full_unstemmed | A method for sorting of spanning trees |
| title_short | A method for sorting of spanning trees |
| title_sort | method for sorting of spanning trees |
| topic | expert estimation pair-wise comparison matrix spanning tree graph diameter Prüfer code |
| topic_facet | експертне оцінювання матриця парних порівнянь покривне дерево діаметр графа код Прюфера expert estimation pair-wise comparison matrix spanning tree graph diameter Prüfer code |
| url | https://drsp.ipri.kiev.ua/article/view/358849 |
| work_keys_str_mv | AT kadenkosv amethodforsortingofspanningtrees AT kadenkosv metodsortuvannâpokrivnihderev AT kadenkosv methodforsortingofspanningtrees |