Date Added: Jun 2011
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.