MAXIMIZING FLOW THROUGH A NETWORK WITH NODE AND ARC CAPACITIES

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 Fulkerson's labeling method.

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Jul 01, 1967
Accession Number
AD0657011

Entities

People

  • R. D. Wollmer

Organizations

  • RAND Corporation

Tags

DTIC Thesaurus Topics

  • Air Force
  • Algorithms
  • Computer Programming
  • Computers
  • Core Storage
  • Corporations
  • Equations
  • Flow Network
  • Heuristic Methods
  • Iterations
  • Linear Programming
  • Network Science
  • Sequences
  • Simplex Method
  • Transportation
  • United States

Readers

  • Computer Networking
  • Operations Research