Solving the Shortest Total Path Length Spanning Tree Problem Using the Modified Sollin and Modified Dijkstra Algorithms
Open Access
- 1 October 2023
- journal article
- research article
- Published by ARTS Publishing in Science and Technology Indonesia
- Vol. 8 (4) , 684-690
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.Keywords
This publication has 13 references indexed in Scilit:
- Finding bounded diameter minimum spanning tree in general graphsComputers & Operations Research, 2022
- A novel approach for agricultural decision making using graph coloringSN Applied Sciences, 2019
- Grouping Method Using Graph Theory for Agricultural Workers Engaging in Manual TasksJournal of Advanced Agricultural Technologies, 2018
- An artificial bee colony algorithm for the minimum routing cost spanning tree problemSoft Computing, 2011
- Phylogenetic graph models beyond treesDiscrete Applied Mathematics, 2009
- A fast algorithm for computing minimum routing cost spanning treesComputer Networks, 2008
- Application of Phylogenetic Networks in Evolutionary StudiesMolecular Biology and Evolution, 2005
- Edge sets: an effective evolutionary coding of spanning treesIEEE Transactions on Evolutionary Computation, 2003
- A multiperiod degree constrained minimal spanning tree problemEuropean Journal of Operational Research, 2002
- Exact algorithms for minimum routing cost treesNetworks, 2002