Solving the Shortest Total Path Length Spanning Tree Problem Using the Modified Sollin and Modified Dijkstra Algorithms
Article Sidebar
Keywords:
-
Shortest Total Path Length Spanning Tree Problem, Modified Sollin Algorithm, Modified Dijkstra
Abstract
In a weighted connected graph, the shortest total path length spanning tree problem is a problem when we need to discover the spanning tree with the lowest total cost of all pairwise distances between its vertices. This problem is also known as the minimum routing cost spanning tree (MRCST). In this study, we will discuss the Modified Sollin and Modified Dijkstra Algorithms to solve that problem which implemented on 300 problems are complete graphs of orders 10 to 100 in increments of 10, where every order consists of 30 problems. The results show that the performance of the Modified Dijkstra and the Modified Sollin Algorithms are slightly similar. On orders 10, 20, 30, 60, and 80, the Modified Dijkstra Algorithm performs better than the Modified Sollin, however on orders 40, 50, 70, 90, and 100, the Modified Sollin performs better.
References
Borůvka, O. (1926). O Jistém Problému Minimálním. Práce Moravské Přírodovědecké Společnosti, 3(3); 37–58
Brandes, U. and S. Cornelsen (2009). Phylogenetic Graph Models beyond Trees. Discrete Applied Mathematics, 157(10); 2361–2369
Campos, R. and M. Ricardo (2008). A Fast Algorithm for Computing Minimum Routing Cost Spanning Trees. Computer Networks, 52(17); 3229–3247
de Nooy, W. (2009). Social Network Analysis, Graph Theoretical Approaches To. Encyclopedia of Complexity and System Science; 8231–8245
Elumalai, A. (2020). Graph Theory Applications in Computer Science and Engineering. Malaya Journal of Matematik, (2); 4025–4027
Fischetti, M., G. Lancia, and P. Serafini (2002). Exact Algorithms for Minimum Routing Cost Trees. Networks: An International Journal, 39(3); 161–173
Hieu, N. M., P. Quoc, and N. D. Nghia (2011). An Approach of Ant Algorithm for Solving Minimum Routing Cost Spanning Tree Problem. In Proceedings of the 2nd Symposium on Information and Communication Technology; 5–10
Huson, D. H. and D. Bryant (2006). Application of Phylogenetic Networks in Evolutionary Studies. Molecular Biology and Evolution, 23(2); 254–267
Julstrom, B. A. (2001). The Blob Code: A Better String Coding of Spanning Trees for Evolutionary Search. In Genetic and Evolutionary Computation Conference Workshop Program. Morgan Kaufmann San Francisco; 256–261
Julstrom, B. A. (2005). The Blob Code is Competitive with Edge-Sets in Genetic Algorithms for the Minimum Routing Cost Spanning Tree Problem. In Proceedings of the 7th Annual Conference on Genetic and Evolutionary Computation; 585–590
Kannimuthu, S., D. Bhanu, and K. Bhuvaneshwari (2020). A Novel Approach for Agricultural Decision Making Using Graph Coloring. SN Applied Sciences, 2; 1–6
Kawakura, S. and R. Shibasaki (2018). Grouping Method Using Graph Theory for Agricultural Workers Engaging in Manual Tasks. Journal of Advanced Agricultural Technologies Vol, 5(3); 173 181
Kawatra, R. (2002). A Multiperiod Degree Constrained Minimal Spanning Tree Problem. European Journal of Operational Research, 143(1); 53–63
Kruskal, J. B. (1956). On the Shortest Spanning Subtree of a Graph and the Traveling Salesman Problem. Proceedings of the American Mathematical Society, 7(1); 48–50
Masone, A., M. E. Nenni, A. Sforza, and C. Sterle (2019). The Minimum Routing Cost Tree Problem: State of the Art and a Core-Node Based Heuristic Algorithm. Soft Computing, 23; 2947–2957
Nøjgaard, N. (2020). Graph Theoretical Problems in Life Sciences. Ph.D. thesis, University of Greifswald, Germany
Prim, R. C. (1957). Shortest Connection Networks and Some Generalizations. The Bell System Technical Journal, 36(6); 1389–1401
Raidl, G. R. and B. A. Julstrom (2003). Edge Sets: An Effective Evolutionary Coding of Spanning Trees. IEEE Transactions on Evolutionary Computation, 7(3); 225–239
Sari, R. P., Wamiliana, A. Junaidi, and W. Susanty (2022). The Diameter and Maximum Link of the Minimum Routing Cost Spanning Tree Problem. Science and Technology Indonesia, 7(4); 481–485
Segal, M. and O. Tzfaty (2022). Finding Bounded Diameter Minimum Spanning Tree in General Graphs. Computers & Operations Research, 144; 105822
Singh, A. (2008). A New Heuristic for the Minimum Routing Cost Spanning Tree Problem. In 2008 International Conference on Information Technology. IEEE; 9–13
Singh, A. and S. Sundar (2011). An Artificial Bee Colony Algorithm for the Minimum Routing Cost Spanning Tree Problem. Soft Computing, 15; 2489–2499
Singh, R. P. (2014). Application of Graph Theory in Computer Science and Engineering. International Journal of Computer Applications, 104(1); 10–13
Tan, Q. P. (2012a). A Genetic Approach for Solving Minimum Routing Cost Spanning Tree Problem. International Journal of Machine Learning and Computing, 2(4); 410
Tan, Q. P. (2012b). A Heuristic Approach for Solving Minimum Routing Cost Spanning Tree Problem. International Journal of Machine Learning and Computing, 2(4); 406
Wamiliana, W., M. Usman, F. Elfaki, and M. Azram (2015a). Some Greedy Based Algorithms for Multi Periods Degree Constrained Minimum Spanning Tree Problem. ARPN Journal of Engineering and Applied Sciences, 10(21); 10147–10152
Wamiliana, W., M. Usman, D. Sakethi, R. Yuniarti, and A. Cucus (2015b). The Hybrid of Depth First Search Technique and Kruskal’s Algorithm for Solving the Multiperiod Degree
Constrained Minimum Spanning Tree Problem. In 2015 4th International Conference on Interactive Digital Media (ICIDM). IEEE; 1–4
Wamiliana, W., M. Usman, W. Warsito, W. Warsono, and J. I. Daoud (2020). Using Modification of Prim’s Algorithm and Gnu Octave and to Solve the Multiperiods Installation Problem. IIUM Engineering Journal, 21(1); 100–112
Brandes, U. and S. Cornelsen (2009). Phylogenetic Graph Models beyond Trees. Discrete Applied Mathematics, 157(10); 2361–2369
Campos, R. and M. Ricardo (2008). A Fast Algorithm for Computing Minimum Routing Cost Spanning Trees. Computer Networks, 52(17); 3229–3247
de Nooy, W. (2009). Social Network Analysis, Graph Theoretical Approaches To. Encyclopedia of Complexity and System Science; 8231–8245
Elumalai, A. (2020). Graph Theory Applications in Computer Science and Engineering. Malaya Journal of Matematik, (2); 4025–4027
Fischetti, M., G. Lancia, and P. Serafini (2002). Exact Algorithms for Minimum Routing Cost Trees. Networks: An International Journal, 39(3); 161–173
Hieu, N. M., P. Quoc, and N. D. Nghia (2011). An Approach of Ant Algorithm for Solving Minimum Routing Cost Spanning Tree Problem. In Proceedings of the 2nd Symposium on Information and Communication Technology; 5–10
Huson, D. H. and D. Bryant (2006). Application of Phylogenetic Networks in Evolutionary Studies. Molecular Biology and Evolution, 23(2); 254–267
Julstrom, B. A. (2001). The Blob Code: A Better String Coding of Spanning Trees for Evolutionary Search. In Genetic and Evolutionary Computation Conference Workshop Program. Morgan Kaufmann San Francisco; 256–261
Julstrom, B. A. (2005). The Blob Code is Competitive with Edge-Sets in Genetic Algorithms for the Minimum Routing Cost Spanning Tree Problem. In Proceedings of the 7th Annual Conference on Genetic and Evolutionary Computation; 585–590
Kannimuthu, S., D. Bhanu, and K. Bhuvaneshwari (2020). A Novel Approach for Agricultural Decision Making Using Graph Coloring. SN Applied Sciences, 2; 1–6
Kawakura, S. and R. Shibasaki (2018). Grouping Method Using Graph Theory for Agricultural Workers Engaging in Manual Tasks. Journal of Advanced Agricultural Technologies Vol, 5(3); 173 181
Kawatra, R. (2002). A Multiperiod Degree Constrained Minimal Spanning Tree Problem. European Journal of Operational Research, 143(1); 53–63
Kruskal, J. B. (1956). On the Shortest Spanning Subtree of a Graph and the Traveling Salesman Problem. Proceedings of the American Mathematical Society, 7(1); 48–50
Masone, A., M. E. Nenni, A. Sforza, and C. Sterle (2019). The Minimum Routing Cost Tree Problem: State of the Art and a Core-Node Based Heuristic Algorithm. Soft Computing, 23; 2947–2957
Nøjgaard, N. (2020). Graph Theoretical Problems in Life Sciences. Ph.D. thesis, University of Greifswald, Germany
Prim, R. C. (1957). Shortest Connection Networks and Some Generalizations. The Bell System Technical Journal, 36(6); 1389–1401
Raidl, G. R. and B. A. Julstrom (2003). Edge Sets: An Effective Evolutionary Coding of Spanning Trees. IEEE Transactions on Evolutionary Computation, 7(3); 225–239
Sari, R. P., Wamiliana, A. Junaidi, and W. Susanty (2022). The Diameter and Maximum Link of the Minimum Routing Cost Spanning Tree Problem. Science and Technology Indonesia, 7(4); 481–485
Segal, M. and O. Tzfaty (2022). Finding Bounded Diameter Minimum Spanning Tree in General Graphs. Computers & Operations Research, 144; 105822
Singh, A. (2008). A New Heuristic for the Minimum Routing Cost Spanning Tree Problem. In 2008 International Conference on Information Technology. IEEE; 9–13
Singh, A. and S. Sundar (2011). An Artificial Bee Colony Algorithm for the Minimum Routing Cost Spanning Tree Problem. Soft Computing, 15; 2489–2499
Singh, R. P. (2014). Application of Graph Theory in Computer Science and Engineering. International Journal of Computer Applications, 104(1); 10–13
Tan, Q. P. (2012a). A Genetic Approach for Solving Minimum Routing Cost Spanning Tree Problem. International Journal of Machine Learning and Computing, 2(4); 410
Tan, Q. P. (2012b). A Heuristic Approach for Solving Minimum Routing Cost Spanning Tree Problem. International Journal of Machine Learning and Computing, 2(4); 406
Wamiliana, W., M. Usman, F. Elfaki, and M. Azram (2015a). Some Greedy Based Algorithms for Multi Periods Degree Constrained Minimum Spanning Tree Problem. ARPN Journal of Engineering and Applied Sciences, 10(21); 10147–10152
Wamiliana, W., M. Usman, D. Sakethi, R. Yuniarti, and A. Cucus (2015b). The Hybrid of Depth First Search Technique and Kruskal’s Algorithm for Solving the Multiperiod Degree
Constrained Minimum Spanning Tree Problem. In 2015 4th International Conference on Interactive Digital Media (ICIDM). IEEE; 1–4
Wamiliana, W., M. Usman, W. Warsito, W. Warsono, and J. I. Daoud (2020). Using Modification of Prim’s Algorithm and Gnu Octave and to Solve the Multiperiods Installation Problem. IIUM Engineering Journal, 21(1); 100–112
Authors
Wamiliana, Sari, R. P., Reformasari, A., Suparman, J., & Junaidi, A. (2023). Solving the Shortest Total Path Length Spanning Tree Problem Using the Modified Sollin and Modified Dijkstra Algorithms. Science and Technology Indonesia, 8(4), 684–690. https://doi.org/10.26554/sti.2023.8.4.684-690
This work is licensed under a Creative Commons Attribution-NonCommercial-ShareAlike 4.0 International License.