Network optimization

Many real-life problems can be modeled as optimization problems in networks. Examples include finding shortest paths, scheduling classes in classrooms, and finding the vulnerability of networks to disconnection because of link and node failures. In this chapter, a number of interesting problems and their algorithms are surveyed. Some of the problems studied are matching, weighted matching, maximum flow in networks, blocking flows, minimum cuts, densest subgraphs, minimum-cost flows, multi-commodity flows, minimum spanning trees, spanners, Light approximate shortest path trees, and graph coloring. Some interesting applications of matching, namely, two processor scheduling, edge covers, and the Chinese postman problem, are also discussed.