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.
Index Terms—Graph, Minimum spanning tree, optimization, Minimum cost, path.
O. T. Arogundade is with the Institute of System Sciences, Chinese Academy of Science, Beijing, China. (phone: +8613521458627; e-mail: firstname.lastname@example.org ).
Sobowale B. was with University of Agriculture, Department of Computer Science, Abeokuta P.M.B. 2240, Ogun State, Nigeria.
T. Akinwale is with the University of Agriculture, Department of Computer Science, Abeokuta P.M.B. 2240, Ogun State, Nigeria. (e-mail: email@example.com )
Cite: Arogundade O. T., Sobowale B., and Akinwale A. T., "Prim Algorithm Approach to Improving Local Access Network in Rural Areas," International Journal of Computer Theory and Engineering vol. 3, no. 3, pp. 413-417, 2011.