The Diameter and Maximum Link of the Minimum Routing Cost Spanning Tree Problem
Article Sidebar
Keywords:
-
Diameter, Cost Routing, Campos Algorithm, Spanning Potential, Maximum Link
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). E cient 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
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). E cient 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
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
This work is licensed under a Creative Commons Attribution-NonCommercial-ShareAlike 4.0 International License.