Comparative Analysis of Some Modified Prim’s Algorithms to Solve the Multiperiod Degree Constrained Minimum Spanning Tree Problem

Objectives: To compare the WAC1, WAC2, and WAC3 algorithms against WADR1, WADR2, WADR3, WADR4, and WADR5 algorithms to solve the Multiperiod Degree Constrained Minimum Spanning Tree. Methods/Statistical analysis: WAC1, WAC2, and WAC3 are algorithms developed by modifying Prim’s algorithm for the Minimum Spanning Tree (MST) and adopting the period of installation/connecting for vertices in the network. In WAC1, WAC2, and WAC3 algorithms we consider the HVTk, the set of vertices that must be connected on kth period, while in WADR5 is not. In WAC1 the vertices in HVTkmust be installed as early as possible, while in WAC2 is not given priority to be connected as soon as possible, but can be any time as long as the connection still on that current period. In WAC3, we adopt the smallest value for 2-path for vertex under consideration to be connected. All algorithm proposed used the same data as used in WADR1, WADR2,WADR3, WADR4 and WADR5. Findings: Since WAC1, WAC2, and WAC3, WADR5 algorithms are based on modified Prim’s algorithm, then the connectivity property is maintained during the process of installation/connection not like WADR1, WADR2, WADR3, and WADR4 where based on kruskal’s. Based on the same data used and connectivity property, the result shows that the performance of WAC2 is the best among the other algorithms developed. Application/Improvements: Considering real life application in the network installation problem, the WAC2 algorithm is one of alternative solutions since it maintains connectivity property and performs best.