Оценка вычислительной сложности алгоритма нахождения критических узлов транспортной сети

Автор(ы): Крыгин А.А., Гребенюк Г.Г.

Выпуск: 120

Рубрика: Сетевые модели в управлении

Год: 2026

Библиография: Крыгин А.А., Гребенюк Г.Г. Оценка вычислительной сложности алгоритма нахождения критических узлов транспортной сети // Управление большими системами. - 2026. - Вып. 120. - С.247-266.

Дата опубликования: 31.03.2026

Ключевые слова: оценка вычислительной сложности алгоритмов на графах, средняя длина пути, среднее количество путей в графе

Аннотация: Одним из важных этапов построения алгоритма для решения некоторой задачи является оценка его вычислительной сложности. Вычислительная сложность алгоритма обычно оценивается в виде зависимости скорости роста времени его работы от объема входных данных. Такая оценка позволяет сравнивать между собой быстродействие алгоритмов решения одной и той же задачи вне зависимости от аппаратной и программной платформы. В данной работе исследуется несколько алгоритмов решения задач для инженерных сетей, моделируемых в виде графа. В работах, посвященных этим алгоритмам, не приводится оценка их вычислительной сложности. Считается общепринятым оценивать объем входных данных алгоритмов на графах через количество вершин и ребер. Рассматриваемые алгоритмы объединяет то, что их вычислительная сложность напрямую зависит не только от количества вершин и~ребер, но и от длины пути и количества путей между двумя вершинами. В работе получены оценки зависимости среднего количества путей и средней длины пути между двумя вершинами графа инженерных сетей. С помощью этих оценок проведен анализ одного из исследуемых алгоритмов, который посвящен решению задачи нахождения критических узлов транспортной сети. Принцип работы этого алгоритма состоит в сведении задачи к эквивалентной задаче целочисленного линейного программирования. Были получены оценки зависимости количества переменных и ограничений от количества узлов транспортной сети.

Author(s): Krygin A., Grebenuk G.

Article title: The evaluation of the computational complexity of the algorithm for finding critical nodes in a transportation network

Issue: 120

Year: 2026

Keywords: computational complexity assessment of graph algorithms, average path length, average number of paths in a graph

Abstract: One of the important stages in developing an algorithm to solve a given problem is assessing its computational complexity. The computational complexity of an algorithm is usually evaluated as the dependence of the growth rate of its running time on the size of the input data. Such an assessment makes it possible to compare the performance of algorithms that solve the same problem, regardless of the hardware and software platform. This work examines several algorithms designed to solve problems for engineering networks modeled as graphs. In studies dedicated to these algorithms, their computational complexity is not provided. It is generally accepted that the input size of graph algorithms is evaluated based on the number of vertices and edges. What the considered algorithms have in common is that their computational complexity depends not only on the number of vertices and edges, but also on the path length and the number of paths between two vertices. The study provides estimates for the dependence of the average number of paths and the average path length between two vertices in engineering network graphs. Using these estimates, an analysis was performed for one of the investigated algorithms, which addresses the problem of identifying critical nodes in a transportation network. The principle of operation of this algorithm is to reduce the problem to an equivalent integer linear programming problem. Estimates were obtained for how the number of variables and constraints depends on the number of nodes in the transportation network.