DID YOU KNOW? DTIC has over 3.5 million final reports on DoD funded research, development, test, and evaluation activities available to our registered users. Click
HERE to register or log in.
Accession Number:
AD0745875
Title:
Duality and the Maximal Flow Capacity of a General Network
Descriptive Note:
Technical rept.
Corporate Author:
NAVAL POSTGRADUATE SCHOOL MONTEREY CA
Report Date:
1971-12-27
Pagination or Media Count:
39.0
Abstract:
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.
Distribution Statement:
APPROVED FOR PUBLIC RELEASE