The Complexity of the Maximum Network Flow Problem
This thesis deals with the computational complexity of the maximum network flow problem. We first introduce the basic concepts and fundamental theorems upon which the study of "max-flow" has been built. We then trace the development of max-flow algorithms from the original "labeling...
| Main Author: | |
|---|---|
| Other Authors: | |
| Published: |
2023
|
| Online Access: | https://hdl.handle.net/1721.1/149513 |
| Summary: | This thesis deals with the computational complexity of the maximum network flow problem. We first introduce the basic concepts and fundamental theorems upon which the study of "max-flow" has been built. We then trace the development of max-flow algorithms from the original "labeling algorithm" of Ford and Fulkerson, through a recent 0 (V-E-log 2 V) algorithm due to Galil and Naamad. |
|---|