EMPIRICAL ANALYSIS OF FACTORS AFFECTING THE PERFORMANCE OF MINIMUM SPANNING TREE ALGORITHMS USING PRINCIPAL COMPONENT

Abstract

The Minimum Spanning Tree (MST) of a graph is the cheapest subset of edges that keeps the graph in one connected component. The significant impact of overall efficiency of a minimum spanning tree is hugely determined by the efficiency of some selected factors such as time taken, memory usage and number of edges visited. However, the level at which each factor affect the performance of the minimum spanning tree is yet to be investigated. The experimentation evaluation was performed on the MST algorithms (Borukva, Kruskal, Prim and Reverse-Delete) by varying the input routes of Lagos State and Federal Capital Territory Road line distances, such that data were generated. Seventy two data samples were obtained from the experiments. The MST algorithms studied were implemented using Java Programming Language. The performance analysis of Borukva, Kruskal, Prim and Reverse-Delete spanning techniques were evaluated based on time taken, memory usage and number of edges visited. Statistical analysis was further performed on the evaluation results using Factor analysis by principal component for the analysis of the generated data. The percentages of variance based on time taken, memory usage and number of edges visited for Borukva were 84.90%, 14.40% and 0.65%, respectively, while the corresponding values for Kruskal were 82.30%, 30.80% and 10.58%, respectively. Also, the percentages of variance based on time taken, memory usage and number of edges visited for Prim were 86.10%, 13.10% and 0.81% respectively, while the corresponding values for Reverse-Delete were 58.70%, 17.50% and 0.13%. The percentage of variance forms the basis for establishing the level of contribution of each factor towards the performance of the MST algorithms. The study revealed that main factor affecting the efficiency of minimum spanning tree algorithm was time taken.