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

Personal Author(s):

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.

Subject Categories:

  • Operations Research

Distribution Statement:

APPROVED FOR PUBLIC RELEASE