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

Reni Permata Sari (Postgraduate Program, Faculty of Mathematics and Natural Sciences, Universitas Lampung, 35145, Indonesia)
Wamiliana (Department of Mathematics, Faculty of Mathematics and Natural Sciences, Universitas Lampung, Lampung, 35145, Indonesia)
Akmal Junaidi (Department of Computer Science, Faculty of Mathematics and Natural Sciences, Universitas Lampung, Lampung, 35145, Indonesia)
Wiwin Susanty (Faculty of Computer Sciences, Universitas Bandar Lampung, Lampung, 35142, Indonesia)

Science and Technology Indonesia
Vol. 7 No. 4 (2022): October

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.