On the Maximal Sets of the Shortest Vertex-Independent Paths

The paper proposes a method for finding the maximum set of the shortest vertex-independent paths between the vertices of a graph. The application area of the method includes algorithms for obtaining the stability estimation of the communication network, estimation of the bandwidth capacity of the communication direction at channel switching. All these algorithms are extremely important in the process of designing and/or modernizing the communication network when solving the problems of finding redundant 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. It is also dictated by the low efficiency of existing algorithms for finding reserve routes, which are based on algorithms for finding the shortest paths between the vertices of the graph of the communication network. It is shown that the problem of searching for reserve routes should be searched for comprehensively, rather than sequentially using the algorithm for finding the shortest path. Since for the communication network, conditionally speaking, it is more important to have two non-shortest routes, which reserve each other, than one shortest route, which “kills” two potentially available routes. And the construction of a reserve route is a resource-intensive activity in the general case for high-dimensional communication networks. The proposed method of finding the maximum set of shortest vertex-independent paths on communication networks of real scales has been tested, which showed its high efficiency and the possibility of using it in resource-intensive problems related to the stability of the communication network, as well as in flow distribution and routing problems. #COMESYSO1120.