Maintaining Minimum Spanning Trees in Fully Dynamic Graphs
Keywords:
Minimum Spanning Tree, MST, Dynamic Algorithm.Abstract
Graphs are mathematical structures utilized in a variety of contexts. Numerous applications have emerged in recent years that require the processing of large dynamic graphs whose structure and properties are continuously evolving. communication, Social, and transportation networks are examples of such applications. The minimum spanning tree (MST) problem is among the most difficult challenges in dynamic graphs at a large scale. The MST problem is notoriously difficult to solve with traditional (algorithmically static) methods, especially on large dynamic graphs that undergo frequent changes. Accordingly, we propose an efficient and fully dynamic MST algorithm for large dynamic graphs in this paper. In light of this, the purpose of this paper is to present an efficient and fully dynamic MST algorithm designed for use with large dynamic graphs. First, we describe our algorithm, then we evaluate the proposed solution. In addition, we present a comprehensive experimental examination of our solution.
Downloads
References
Cloud computing services - amazon web services (aws). 5
M Alshammari and Abdelmounaam Rezgui. A single-source shortest path algorithm for dynamic graphs. AKCE International Journal of Graphs and Combinatorics, 17(3):1063–1068, 2020. 1
Giuseppe Amato, Giuseppe Cattaneo, and Giuseppe F Italiano. Experimental analysis of dynamic minimum spanning tree algorithms. In SODA, volume 97, pages 314–323. Citeseer, 1997. 2
Giuseppe Cattaneo, Pompeo Faruolo, U Ferraro Petrillo, and Giuseppe F Italiano. Maintaining dynamic minimum spanning trees: An experimental study. Discrete Applied Mathematics, 158(5):404–425, 2010. 1, 2
Camil Demetrescu and Giuseppe F Italiano. A new approach to dynamic all pairs shortest paths. Journal of the ACM (JACM), 51(6):968–992, 2004. 4.3
Camil Demetrescu and Giuseppe F Italiano. Experimental analysis of dynamic all pairs shortest path algorithms. ACM Transactions on Algorithms (TALG), 2(4):578–601, 2006. 5.1
David Eppstein, Zvi Galil, Giuseppe F Italiano, and Amnon Nissenzweig. Sparsification—a technique for speeding up dynamic graph algorithms. Journal of the ACM (JACM), 44(5):669–696, 1997. 2
Greg N Frederickson. Data structures for on-line updating of minimum spanning trees. In Proceedings of the fifteenth annual ACM symposium on Theory of computing, pages 252–257, 1983. 1, 2
Greg N Frederickson. Ambivalent data structures for dynamic 2-edge-connectivity and k smallest spanning trees. SIAM Journal on Computing, 26(2):484–538, 1997. 2
Daniele Frigioni, Alberto Marchetti-Spaccamela, and Umberto Nanni. Fully dynamic algorithms for maintaining shortest paths trees. Journal of Algorithms, 34(2):251–281, 2000. 4.3
Monika Rauch Henzinger and Valerie King. Fully dynamic 2-edge connectivity algorithm in polylogarithmic time per operation. SRC Technical Note, 4, 1997. 2
Jacob Holm, Kristian De Lichtenberg, and Mikkel Thorup. Poly-logarithmic deterministic fully-dynamic algorithms for connectivity, minimum spanning tree, 2-edge, and biconnectivity. Journal of the ACM (JACM), 48(4):723–760, 2001. 1, 2
Bruce M Kapron, Valerie King, and Ben Mountjoy. Dynamic graph connectivity in polylogarithmic worst case time. In Proceedings of the twenty-fourth annual ACM-SIAM symposium on Discrete algorithms, pages 1131–1142. SIAM, 2013. 2
Valerie King. Fully dynamic algorithms for maintaining all-pairs shortest paths and transitive closure in digraphs. In 40th Annual Symposium on Foundations of Computer Science (Cat. No. 99CB37039), pages 81–89. IEEE, 1999. 4.3
Jure Leskovec and Andrej Krevl. SNAP Datasets: Stanford large network dataset collection. http://snap.stanford.edu/data, June 2014. 5.1
Danupon Nanongkai, Thatchaphol Saranurak, and Christian Wulff-Nilsen. Dynamic minimum spanning forest with subpolynomial worst-case update time. In 2017 IEEE 58th Annual Symposium on Foundations of Computer Science (FOCS), pages 950–961. IEEE, 2017. 2
Ganesan Ramalingam and Thomas Reps. On the computational complexity of dynamic graph problems. Theoretical Computer Science, 158(1–2):233–277, 1996. 4.3
Celso C Ribeiro and Rodrigo F Toso. Experimental analysis of algorithms for updating minimum spanning trees on graphs subject to changes on edge weights. In Experimental Algorithms: 6th International Workshop, WEA 2007, Rome, Italy, June 6-8, 2007. Proceedings 6, pages 393–405. Springer, 2007. 1, 2, 5
Mikkel Thorup. Worst-case update times for fully-dynamic all-pairs shortest paths. In Proceedings of the thirty-seventh annual ACM symposium on Theory of computing, pages 112–119. ACM, 2005. 4.3
Christian Wulff-Nilsen. Fully-dynamic minimum spanning forest with improved worst-case update time. In Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, pages 1130–1143, 2017. 1, 2
Aya Zaki, Mahmoud Attia, Doaa Hegazy, and Safaa Amin. Comprehensive survey on dynamic graph models. International Journal of Advanced Computer Science and Applications, 7(2):573–582, 2016. 1
Downloads
Published
How to Cite
Issue
Section
License
This work is licensed under a Creative Commons Attribution-ShareAlike 4.0 International License.
All papers should be submitted electronically. All submitted manuscripts must be original work that is not under submission at another journal or under consideration for publication in another form, such as a monograph or chapter of a book. Authors of submitted papers are obligated not to submit their paper for publication elsewhere until an editorial decision is rendered on their submission. Further, authors of accepted papers are prohibited from publishing the results in other publications that appear before the paper is published in the Journal unless they receive approval for doing so from the Editor-In-Chief.
IJISAE open access articles are licensed under a Creative Commons Attribution-ShareAlike 4.0 International License. This license lets the audience to give appropriate credit, provide a link to the license, and indicate if changes were made and if they remix, transform, or build upon the material, they must distribute contributions under the same license as the original.
