International Journal of Computer Theory and Engineering

Abstract

This paper presents an application of Prim’s Algorithm to local access network in rural areas. The minimum spanning tree problem has important applications in network design which has been extensively studied in literature. The minimum spanning tree problem on a graph with edge costs and vertex profits asks for a sub tree maximizing the difference between the total cost of all edges in the sub tree and the total profits of all vertices contained in the sub tree. Minimum spanning tree problem appears in the design of utility networks (e.g. bus services, electrifications) where villages and the network connecting them have to be chosen in the most profitable way. The application of Prim’s algorithms is demonstrated to the design of local access networks in a particular local government area of about 88 villages. The case study is analyzed and interesting results are obtained. The results obtained justify the need to apply this kind of algorithm for efficiency and profitability.