This research is to develop and analyze efficient algorithms for a variety of standard network flow problems. The algorithms are to be analyzed from both empirical and theoretical points of view. Comparison measures used to evaluate the algorithms are worst case performance, average case performance and empirical performance based on computational experiments. Both sequential and parallel algorithm implementation is to be investigated. One of the major tools to be used is scaling, solving a sequence of problems that are closer and closer to the original problem and reoptimization of the solution of the previous problem is used to solve the next problem. Important new results to impact the current state-of-the-art knowledge and improve the technology base in network flow theory should prove successful in this research.
