Graphical algorithms for solving minimal cost network flow problems and applications

Author

David Richard Woodcox

Date of Award

8-1996

Degree Type

Thesis

Degree Name

Master of Science

Major

Mathematics

Major Professor

Yueh-er Kuo

Committee Members

Anderson, Sundburg

Abstract

This paper presents two algorithms, based on the simplex algorithm, which can be used to minimize linear functions of flow in a directed network or digraph. These algorithms can be preformed directly on the graph, and hence eliminate the need for simplex tableaus, and increase solution speed. In addition, the paper gives several examples of important applications for both of the algorithms. These include the minimal cost network flow problem, the shortest path problem, the traveling salesman problem, and a scheduling problem (longest path problem).

Recommended Citation

Woodcox, David Richard, "Graphical algorithms for solving minimal cost network flow problems and applications. " Master's Thesis, University of Tennessee, 1996.
https://trace.tennessee.edu/utk_gradthes/11008