Duality and the Maximal Flow Capacity of a General Network
NAVAL POSTGRADUATE SCHOOL MONTEREY CA
Pagination or Media Count:
The use of the dual graph in determining the maximal flow capacity of an undirected source-sink planar network has been extended to general networks. A directed dual graph is first defined for directed source-sink planar networks such that the length of the shortest route through this dual is equal to the maximal flow capacity of the primal. The construction of the dual is then modified to handle flows in networks which are not source-sink planar. An algorithm is presented for finding the modified shortest route through this dual having a length equal to the maximal flow capacity of the primal network.
- Operations Research