About one problem of analysis of the topology of communication networks
Abstract
The paper discusses heuristic nonlinear algorithms for checking 2-multiple edge connectivity. This is the term we introduce, a graph has 2-multiple edge connectivity in the case when there are at least 2 edge-independent paths between any two of its vertices; it is important to note that this concept does not coincide with the concept of edge $2$-connectivity of a graph, which is more studied in the literature.
For the last problem, polynomial algorithms have been previously described in the literature, and their small modifications also give algorithms for solving "our" problem. However, we do not consider them: they are quite complex to implement, and we need algorithms in which, at the request of the customer, it is often necessary to make some modifications during its execution.
In the problems considered in this paper, we use such auxiliary algorithms that can be called heuristic; as a result, the full versions of the algorithms under consideration can also be called heuristic. In the paper we consider 3 different groups of algorithms designed to test 2-multiple edge connectivity.
Namely, first we give explicit algorithms for such verification, i.e. algorithms in which the necessary paths are constructed explicitly. Next, in the following algorithm, we check the possible existence of a common cycle for any two vertices of a given graph. The third algorithm is that we check 2-multiple edge connectivity based, firstly, on the absence of bridges and, secondly, on the presence of at least some cycle involving it for any vertex of the graph.
We present a scheme for proving the equivalence of these three algorithms, and after that, a brief description of computational experiments.
Full Text:
PDF (Russian)References
Harary F. Graph theory // Massachusetts: Addison-Wesley Publ., 1969. – 274 p.
Diestel R. Graph theory // Heidelberg: Springer-Verlag, 1997. – 358 p.
Gera R., Hedetniemi S., Larson C. (Eds.) Graph Theory. Favorite Conjectures and Open Problems – 1. Berlin: Springer, 2016 – 291 p.
Karpov D. Graph theory // Saint Petersburg: Publishing House of the St. Petersburg Branch Mathematical Institute named after V. A. Steklov of Russian Academy of Sciences, 2017. – 482 p. (in Russian)
Gera R., Hedetniemi S., Larson C. (Eds.) Graph Theory. Favorite Conjectures and Open Problems – 2. Berlin: Springer, 2018. – 281 p.
Needham M., Hodler E. Graph Algorithms. Practical Examples in Apache Spark and Neo4j. Berlin: O’Reilly Media, Inc., 2019 – 300 p.
Bulynin A., Melnikov B., Meshchanin V., Terentyeva 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. – P. 34–40. (in Russian)
Melnikov B., Terentyeva Yu. Building communication networks: on the application of the Kruskal’s algorithm in the problems of large dimensions // In: IOP Conference Series: Materials Science and Engineering. Krasnoyarsk Science and Technology City Hall. – Krasnoyarsk, Russian Federation. – 2021. – P. 12089.
Melnikov B., Terentyeva Yu. Building an optimal spanning tree as a tool to ensure the stability of the communication network // News of higher educational institutions. Volga region. Technical sciences. – 2021. – No. 1 (57). – P. 36–45. (in Russian)
Starikov P. About the set of independent paths in a graph //Informatization and communication. – 2021. – No. 6. – P. 176–181. (in Russian)
Melnikov B., Sayfullina E. Application of a multiheuristic approach for random generation of a graph with a given degree vector //News of higher educational institutions. Volga region. Physical and mathematical sciences. – 2013. – No. 3 (27). – P. 70–83. (in Russian)
Melnikov B., Sayfullina E. , Terentyeva Yu., Churikova N. Application of random graph generation algorithms to study the reliability of communication networks // Informatization and communication. – 2018. – No. 1. – P. 71–80. (in Russian)
Melnikov B., Radionov A. On the choice of strategy in nondeterministic antagonistic games // Programming (Russian Academy of Sciences Ed.). – 1998. – No. 5. – P. 55–68. (in Russian)
Melnikov B., Romanov N. Once again about heuristics for the traveling salesman problem // Theoretical problems of computer science and its applications. – 2001. – No. 4. – P. 81–95. (in Russian)
Melnikov B., Melnikova E. Clustering of situations in real-time algorithms for discrete optimization problems // Control systems and information technologies. – 2007. – No. 2 (28). P. 16–20. (in Russian)
Melnikov B., Eirih S. An approach to combining an incomplete branch and boundary method and a simulation normalization algorithm // Bulletin of the Voronezh State University. Series: System Analysis and Information Technology. – 2010. – No. 1. P. 35–38. (in Russian)
Tarjan R. A note on finding the bridges of a graph // Information Processing Letters. – 1974. – Vol. 2. No. 6. – P. 160–161.
Westbrook J., Tarjan R. Maintaining bridge-connected and biconnected components on-line // Algorithmica. – 1992. – Vol. 7. No. 5-6. – P. 433–464.
Refbacks
- There are currently no refbacks.
Abava Кибербезопасность IT Congress 2024
ISSN: 2307-8162