A method for sorting of spanning trees

• Datum: 2026
• 1. Verfasser: Каденко, С. В.
• Format: Artikel
• Sprache: Ukrainisch
• Veröffentlicht: Інститут проблем реєстрації інформації НАН України 2026
• Schlagworte: expert estimation; pair-wise comparison matrix; spanning tree; graph diameter; Prüfer code
• Online Zugang: https://drsp.ipri.kiev.ua/article/view/358849
• Назва журналу: Data Recording, Storage & Processing

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.