Finding critical nodes in a transportation network based on constructing a closed region

The problem of finding critical nodes in a transportation network is considered, which is solved by maximizing the generalized cost of travel, which depends on the demand for movement and the cost of travel between each pair of network nodes. The proposed method in the paper is an improvement of exhaustive search, the main difficulty of which lies in the repeated computation of the matrix of minimum travel costs. The method consists of extracting a closed set of vertices from the original graph. The extraction of a closed set of vertices allows for graph reduction, decomposition of the corresponding matrices, and separate computations of sub-matrices. These transformations have helped reduce computations during the search for options. A general algorithm for finding critical nodes has been constructed and optimized. The closed set is divided into an internal and boundary subset. It has been shown that the algorithm works fastest with a minimum size of the boundary subset and an optimal size of the internal subset, for which a corresponding algorithm has been proposed to determine. An algorithm for constructing and expanding the closed set is also proposed, based on which an approximate algorithm for finding the optimal closed set is constructed. It has been shown that the complexity of finding the optimal closed set is much lower than the complexity of the improved exhaustive search method.