Maximum set shortest vertex-independent paths

Abstract

The article proposes a method for finding the maximum set of shortest vertex-independent paths between the vertices of a graph. The scope of the method includes procedures for obtaining an assessment of the stability of the communication network, assessing the bandwidth of the communication direction during channel switching. All these procedures are extremely important in the process of designing and/or upgrading a communication network when solving problems of finding backup paths. The need to develop the proposed method is primarily due to technical and economic factors associated with the organization of backup routes on communication networks. And it is also dictated by the low efficiency of existing algorithms for finding backup routes, which are based on algorithms for finding the shortest paths between the vertices of the communication network graph. It is shown that the problem of finding backup routes must be searched for comprehensively, and not sequentially using the algorithm for finding the shortest path. Because for a communication network, relatively speaking, it is more important to have two shortest routes that reserve each other than one shortest one that "kills" two potentially available routes. And building a backup route is a resource–intensive event in the general case for high-dimensional communication networks. The proposed method of finding the maximum set of shortest vertex-independent paths on real-scale communication networks has been tested, which has shown its high efficiency and the possibility of using it in resource-intensive tasks related to the stability of the communication network, as well as in flow distribution and routing tasks.