Accession Number:

AD0657011

Title:

MAXIMIZING FLOW THROUGH A NETWORK WITH NODE AND ARC CAPACITIES

Descriptive Note:

Corporate Author:

RAND CORP SANTA MONICA CA

Personal Author(s):

Report Date:

1967-07-01

Pagination or Media Count:

40.0

Abstract:

A method for maximizing the flow from source to destination along a transportation network whose nodes and arcs have limited capacities. An algorithm is derived that eliminates the need for artificial arcs and nodes used in the flow-augmenting method of Fulkerson and Ford. This simplification should provide a substantial savings in computer time and core storage. The problem is formulated as a linear program. For all nodes other than the source and sink, the node capacity may be expressed either as the flow into or out of the node, since these two quantities are equal. For the source and sink, the node capacity must be expressed in terms of the greater of the two quantities. Thus the source node capacity limits flow out of the source, while the sink capacity limits flow into the sink. The solution method used, a cut set approach, is a generalization of Ford and Fulkersons labeling method.

Subject Categories:

  • Electrical and Electronic Equipment
  • Computer Hardware
  • Computer Systems

Distribution Statement:

APPROVED FOR PUBLIC RELEASE