Maximum set shortest vertex-independent paths

Y.Y. Terentyeva


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.

Full Text:

PDF (Russian)


Yasinsky S.A., Sokolov V.M. Modification of algorithms for finding shortest paths in the transport network of the telecommunication system for the dissemination of geoinformation // Information and Space, No. 2, 2012, pp. 6-11.

Nazarov A. N., Sychev K. I. Models and methods for calculating the quality indicators of the functioning of node equipment and structural and network parameters of next-generation communication networks. – Krasnoyarsk: Polikom, 2010 – 389 p.

Dyshlenko S.G. Routing in transport networks // ITNOU: Information Technologies in Science, Education and Management, 2018, No. 1, pp.15-20.

Tsvetkov K.Yu., Makarenko S.I., Mikhailov R.L. Formation of backup paths based on the Dijkstra algorithm in order to increase the stability of

information and telecommunication networks // Information and control systems, 2014, No. 2.

Terentyeva Yu.Yu. Determination of the maximum set of independent simple paths between the vertices of the graph. International Scientific Journal "Modern Information Technologies and IT Education", [S.L.], vol. 17, No. 2.- 2021. ISSN 2411-1473.

Bulynin A.G., Melnikov B.F., Meshchanin V.Yu., Terentyeva Yu.Yu. Optimization problems arising in the design of high–dimensional communication networks and some heuristic methods for their solution // Informatization and Communication. – 2020. – No. 1. - pp. 34-40.

Kormen T., Leiserson Ch., Rivest R., Stein K. Algorithms: construction and analysis. / Moscow: Williams Publishing House, 2011— 1296 p.

Harari F. Graph theory.- M.: Mir, 1973 – 300p.

Ford L., Fulkerson D. Flows in networks. – Moscow: Mir, 1966.-277p.

Wentzel E.S. Probability Theory. - M.: Nauka, 1969.

Melnikov B.F., Terentyeva Yu.Yu. Building an optimal spanning tree as a tool for ensuring the stability of a communication network // News of higher educational institutions. Volga region. Technical sciences.-2021.-No. 1 – pp. 36-45.


  • There are currently no refbacks.

Abava  Кибербезопасность MoNeTec 2024

ISSN: 2307-8162