The Diameter and Maximum Link of the Minimum Routing Cost Spanning Tree Problem

Reni Permata Sari, Wamiliana, Akmal Junaidi, Wiwin Susanty

Abstract

The minimum routing cost spanning tree (MRCST) is a spanning tree that minimizes the sum of pairwise distances between its vertices given a weighted graph. In this study, we use Campos Algorithm with slight modifications on the coefficient of spanning potential. Those algorithms were implemented on a random table problem data of complete graphs of order 10 to 100 in increments of 10. The goal is to find the diameter (the largest shortest path distance) and the maximum link (the maximum number of edges connecting two vertices) in the spanning tree solution of MRCST. The result shows that a slight modification of the spanning potential coefficients gives better solutions.

References

Boruvka, O. (1926). O Jistém Problému Minimálním. ˘ Práce Moravské Přírodovědecké Společnosti, 3(3); 37–58

Campos, R. and M. Ricardo (2008). A Fast Algorithm for Computing Minimum Routing Cost Spanning Trees. Computer Networks, 52(17); 3229–3247

Chen, K., Y. E. Hsieh, and P. J. Lu (2013). Parallel Approximation Algorithms for Minimum Routing Cost Spanning Tree. International Journal of Computational Science and Engineering, 8(4); 336–348

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. Proceedings of the Second Symposium on Information and Communication Technology; 5–10

Julstrom, B. A. (2001). The Blob Code: a Better String Coding of Spanning Trees for Evolutionary Search. 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. Proceedings of the 7th Annual Conference on Genetic and Evolutionary Computation; 585–590

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

Lin, C. M., Y. Te Tsai, and C. Y. Tang (2006). Balancing Minimum Spanning Trees and Multiple-Source Minimum Routing Cost Spanning Trees on Metric Graphs. Information Processing Letters, 99(2); 64–67

Masone, A., M. E. Nenni, A. Sforza, and C. Sterle (2019). The Minimum Routing Cost Tree Problem. Soft Computing, 23(9); 2947–2957

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

Sattari, S. and F. Didehvar (2013). Variable Neighborhood Search Approach for the Minimum Routing Cost Spanning Tree Problem. International Journal Operations Research, 10(4); 153–160

Sattari, S. and F. Didehvar (2015). A Metaheuristic Algorithm for the Minimum Routing Cost Spanning Tree Problem. Iranian Journal of Operations Research, 6(1); 65–78

Singh, A. (2008). A New Heuristic for the Minimum Routing Cost Spanning Tree Problem. International Conference on Information Technology. IEEE; 9–13

Singh, A. and S. Sundar (2011). An Aartificial Bee Colony Algorithm for the Minimum Routing Cost Spanning Tree Problem. Soft Computing, 15(12); 2489–2499

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

Tan, Q. P. and N. N. Due (2013). An Experimental Study of Minimum Routing Cost Spanning Tree Algorithms. International Conference on Soft Computing and Pattern Recognition (SoCPaR). IEEE; 158–165

Vasudev, C. (2006). Graph Theory with Applications. New Age International

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. The 4th International Conference on Interactive Digital Media (ICIDM); 1–4

Wamiliana, W., M. Usman, W. Warsito, W. Warsono, and J. I. Daoud (2020). Using Modication of Prim’s Algorithm and GNU Octave to Solve the Multiperiods Installation Problem. IIUM Engineering Journal, 21(1); 100–112

Wolf, S. and P. Merz (2010). Ecient Cycle Search for the Minimum Routing Cost Spanning Tree Problem. European Conference on Evolutionary Computation in Combinatorial Optimization. Springer; 276–287

Wu, B. Y. (2002). A Polynomial Time Approximation Scheme for the Two-Source Minimum Routing Cost Spanning Trees. Journal of Algorithms, 44(2); 359–378

Authors

Reni Permata Sari
Wamiliana
wamiliana.1963@fmipa.unila.ac.id (Primary Contact)
Akmal Junaidi
Wiwin Susanty
Sari, R. P. ., Wamiliana, Junaidi, A. ., & Susanty, W. . (2022). The Diameter and Maximum Link of the Minimum Routing Cost Spanning Tree Problem. Science and Technology Indonesia, 7(4), 481–485. https://doi.org/10.26554/sti.2022.7.4.481-485

Article Details