METHOD OF CREATING A MINIMAL SPANNING TREE ON AN ARBITRARY SUBSET OF VERTICES OF A WEIGHTED UNDIRECTED GRAPH
DOI:
https://doi.org/10.15588/1607-3274-2024-1-17Keywords:
network object, weighted undirected graph, connectivity, transitive closure, minimum spanning tree, local optimum, optimization criterion, methodAbstract
Context. The relevance of the article is determined by the need for further development of models for optimal restoration of the connectivity of network objects that have undergone fragmentation due to emergency situations of various origins. The method proposed in this article solves the problematic situation of minimizing the amount of restoration work (total financial costs) when promptly restoring the connectivity of a selected subset of elements of a network object after its fragmentation.
The purpose of the study is to develop a method for creating a minimal spanning tree on an arbitrary subset of vertices of a weighted undirected graph to minimize the amount of restoration work and/or total financial costs when promptly restoring the connectivity of elements that have a higher level of importance in the structure of a fragmented network object.
Method. The developed method is based on the idea of searching for local minima in the structure of a model undirected graph using graph vertices that are not included in the list of base vertices to be united by a minimal spanning tree. When searching for local minima, the concept of an equilateral triangle and a radial structure in such a triangle is used. In this case, there are four types of substructures that provide local minima: first, those with one common base vertex; second, those with two common base vertices; third, those with three common base vertices; fourth, those without common base vertices, located in different parts of the model graph. Those vertices that are not included in the list of basic ones, but through which local minima are ensured, are added to the basic ones. Other vertices (non-basic) along with their incident edges are removed from the structure of the model graph. Then, using one of the well-known methods of forming spanning trees, a minimal spanning tree is formed on the structure obtained in this way, which combines the set of base vertices.
Results. 1) A method for creating a minimal spanning tree on an arbitrary subset of vertices of a weighted undirected graph has been developed. 2) A set of criteria for determining local minima in the structure of the model graph is proposed. 3) The method has been verified on test problems.
Conclusions. The theoretical studies and several experiments confirm the efficiency of the developed method. The solutions developed using the developed method are accurate, which makes it possible to recommend it for practical use in determining strategies for restoring the connectivity of fragmented network objects.
References
Kerigan-Kyrou D. Critical Energy Infrastructure: Operators, NATO, and Facing Future Challenges, Connections: The Quarterly Journal 12, 2013, Vol. 3, pp. 109– 117. DOI: 10.11610/Connections.12.3.06.
Tichý L., Eichler J. Terrorist Attacks on the Energy Sector: The Case of Al Qaeda and the Islamic State, Studies in Conflict & Terrorism, 2018, Vol. 41, No. 6, pp. 450–473. DOI: 10.1080/1057610X.2017.1323469.
Dunn S., Wilkinson S. Hazard Tolerance of Spatially Distributed Complex Networks, Reliability Engineering & System Safety 157, 2017, pp. 1–12. DOI:10.1016/j.ress.2016.08.010.
Varianou Mikellidou C., Shakou L., Boustras G. et al. Energy Critical Infrastructures at Risk from Climate Change: A State-of-the-Art Review, Safety Science, 2018, Vol. 110, Part C, pp. 110–120. DOI: 10.1016/j.ssci.2017.12.022.
Danyk Yu., Maliarchuk T., Briggs Ch. Hybrid War: Hightech, Information and Cyber Conflicts. Connections, The Quarterly Journal 16, 2017, Vol. 2, pp. 5–24. DOI: 10.11610/Connections.16.2.01.
Sulema O. K., Lande D. V. Finding the optimal hierarchy in a quasi-hierarchical graph by centrality criteria, Registration, storage and processing of data, 2015, Vol. 17, No 4, pp. 3–10. ISSN 1560-9189.
Prim R. Shortest connection networks and some generalizations, Bell System Technical Journal, 1957, Vol. 36, No. 6, pp. 1389–1401. DOI: 10.1002/j.15387305.1957.tb01515.x.
Kruskal J. On the Shortest Spanning Subtree of a Graph and the Traveling Salesman Problem, Proc. AMS, 1956, Vol 7, No. 1, pp. 48–50. DOI: 10.1090/S0002-9939-19560078686-7.
Pawan Harish, Narayanan P., Vineet Vibhav, Suryakant Patidar Chapter 7 – Fast Minimum Spanning Tree Computation. GPU Computing Gems Jade Edition, Applications of GPU Computing Series. San Francisco, Morgan Kaufmann, 2012, pp. 77–88. ISBN 9780123859631, DOI: 10.1016/B978-0-12-3859631.00007-1.
Cheriton D., Endre T. Finding minimum spanning trees, SIAM Journal on Computing, 1976, Vol. 5 (4), pp. 724– 742. DOI:10.1137/0205051.
Seth P., Vijaya R. An optimal minimum spanning tree algorithm, Journal of the ACM, 2002, Vol. 49 (1), pp. 16– 34. DOI:10.1145/505241.505243.
Johnson D. Priority queues with update and finding minimum spanning trees, Information Processing Letters, 1975, 4 (3), pp. 53–57. DOI:10.1016/0020-0190(75)900010.
Christofides N. Theory of graphs. Algorithmic approach. Moscow, Mir, 1978, 432 p.
Floyd R. Algorithm 97: Shortest Path, Communications of the ACM, 1961, Vol. 5 (6), 345 p. DOI:10.1145/367766.368168.
Warshall S. Algorithm on Boolean matrices, Journal of the ACM, 1962, Vol. 9 (1), pp. 11–12. DOI:10.1145/321105.321107.
Shimbel A. Structural parameters of communication networks, Bulletin of Mathematical Biophysics, 1953, Vol. 15 (4), pp. 501–507. DOI:10.1007/BF02476438.
Downloads
Published
How to Cite
Issue
Section
License
Copyright (c) 2024 V. M. Batsamut, S. O. Hodlevsky, Yu. P. Babkov, D. A. Morkvin
This work is licensed under a Creative Commons Attribution-ShareAlike 4.0 International License.
Creative Commons Licensing Notifications in the Copyright Notices
The journal allows the authors to hold the copyright without restrictions and to retain publishing rights without restrictions.
The journal allows readers to read, download, copy, distribute, print, search, or link to the full texts of its articles.
The journal allows to reuse and remixing of its content, in accordance with a Creative Commons license СС BY -SA.
Authors who publish with this journal agree to the following terms:
-
Authors retain copyright and grant the journal right of first publication with the work simultaneously licensed under a Creative Commons Attribution License CC BY-SA that allows others to share the work with an acknowledgement of the work's authorship and initial publication in this journal.
-
Authors are able to enter into separate, additional contractual arrangements for the non-exclusive distribution of the journal's published version of the work (e.g., post it to an institutional repository or publish it in a book), with an acknowledgement of its initial publication in this journal.
-
Authors are permitted and encouraged to post their work online (e.g., in institutional repositories or on their website) prior to and during the submission process, as it can lead to productive exchanges, as well as earlier and greater citation of published work.
