Optimization in graphs and networks

This thesis is a study of some optimization techniques in graphs and networks.

Chapter I deals with the problem of finding the shortest paths in graphs of relatively small dimensions.

Chapter II discusses and solves the problem of shortest paths in graphs of large dimensions, which can be partitioned into overlapping subgraphs. The method described in Section 2.3. and 2.4., which is due to the author of this thesis, is a means to partition a large graph into its overlapping subgraphs, and to find the cut sets and minimum cut sets in a graph.

Chapter III deals primarily with network flows. In particular, the problems of maximal flows in a network, and minimal cost flows are discussed.

Chapter IV presents flow charts and Fortran IV Computer Programs for the main algorithms presented in this thesis. These flow charts and programs are developed independently by the author.