ABSTRACT
This chapter examines a number of classical network optimization problems and describes algorithms for their exact or approximate solution. It also presents models and analysis of small-world networks. In an undirected network, the minimum spanning tree problem is the problem of identifying a spanning tree of the network that has the smallest possible sum of edge costs. This problem arises in a number of applications, both as a stand-alone problem and as a sub-problem in more complex problem settings. There are several greedy algorithms for constructing minimum spanning trees, based on the optimality conditions. Minimum spanning tree problems arise both directly and indirectly. For direct applications, the points in a given set are to be connected using the least cost collection of edges. For indirect applications, creative modeling of the original problem recasts it as a minimum spanning tree problem.
