Optimization of the Algorithm for Finding Spanning Trees of a Graph

Authors

  • Dauren Axmetbaev S. Seifullin Kazakh Agro Technical University, Nur-Sultan, Republic of Kazakhstan
  • A. R. Dzhandigulov L.N. Gumilyov Eurasian National University, Nur-Sultan, Republic of Kazakhstan
  • A. D. Akhmetbaev Information Systems Directorate, «Kazakhtelecom» JSC, Almaty, Republic of Kazakhstan

Keywords:

network topology, graph tree

Abstract

The paper presents one of the possible variants of optimization of the algorithm for finding all spanning trees of the graph from the point of view of the application of the results of calculations in the topological study of complex electric power systems.

The first stage of the topological analysis of the network is the search and determination of the values of all possible trees of the graph corresponding to a given energy system. The computational complexity of the algorithm for finding and determining the weights of all spanning graphs increases as the branches and nodes of the power grid network increase.

The main idea of optimization is to build special classes of trees. At the same time, in the process of grouping, parts of future graphs that are "parent" for groups of graphs are allocated and corresponding graphs of significantly smaller dimension are constructed. If the analysis is time-consuming, the grouping process can be applied to each graph found.

Downloads

Published

2019-12-25

Issue

Vol. 2 No. 3 (2019): Energy Systems Research

Section

Articles