Not checkedNot checked for notices yet.
Determination of the Maximum Set Independent Simple Paths between the Vertices of the Graph
Yulia Terentyeva
Современные информационные технологии и IT-образование · 2021
doi:10.25559/sitito.17.202102.308-314 (opens in a new tab)
We email you when a new notice or a question about this paper appears.
Abstract
This article presents an algorithm for determining the maximum number of independent simple paths, as well as the paths themselves, between the given vertices of the graph. This task is extremely important in the theory of communication, its solution is necessary to ensure the stability of the communication network. At the same time, this problem is not considered a separate problem in graph theory. The urgency of solving it is due, firstly, as already noted, the need to increase the stability of the communication network, and, secondly, the fact that for real highly branched communication networks, the use of traditional algorithms for finding independent routes based on finding the shortest paths becomes ineffective. The inefficiency is explained by the fact that in the presence, for example, of two independent routes in large-scale communication networks, traditional algorithms for finding the shortest paths can find only one due to the fact that between the available independent simple paths there are paths through which the found by the standard algorithm (finding the shortest path) path, capturing parts of two available independent routes. A similar effect can be observed in the presence of more than two independent simple paths, when standard algorithms for finding the shortest path can "lose" all simple paths in excess of one. The subject of this article is about fixing this problem.
Abstract licence: CC BY
Reads
Read by people on this page
None yet.
Checked or read by AI through naulon
None yet.
A person counts once a day per paper. We keep no cookie and no address: a reader is a hash that changes every day. Any month under five reads shows no number.
Are you an author?
Is this your paper?
Claim it to add your note and be paid when agents cite it. Free.