Masters Theses
Date of Award
5-2000
Degree Type
Thesis
Degree Name
Master of Science
Major
Mathematics
Major Professor
Yueh-er Kuo
Committee Members
William Wade, Charles Collins
Abstract
This paper looks at several methods for solving network flow problems. The first chapter gives a brief background for linear programming (LP) problems. It includes basic definitions and theorems. The second chapter gives an overview of graph theory including definitions, theorems, and examples.
Chapters 3-5 are the heart of this thesis. Chapter 3 includes algorithms and applications for maximum flow problems. It includes a look at a very important theorem. Maximum Flow/Minimum Cut Theorem. There is also a section on the Augmenting Path Algorithm. Chapter 4 Deals with shortest path problem. It includes Dijsksta's Algorithm and the All-Pairs Labeling Algorithm. Chapter 5 includes information on algorithms and applications for the minimum cost flow(MCF)problem. The algorithms covered include the Cycle Canceling,Successive ShortestPath,and Primal-Dual Algorithms. Each of these chapters 3-5 contain definitions,theorems,and algorithms to solve network flow problems.
Throughout the paper the computer program LINDO is used. It serves a couple of functions. First it is a way of checking each solution. The second use is to expose the reader to a very valuable tool in linear programming.
Recommended Citation
Collins, Randy Lee, "Network flow algorithms and applications. " Master's Thesis, University of Tennessee, 2000.
https://trace.tennessee.edu/utk_gradthes/9313