Duality and the Maximal Flow Capacity of a General Network

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.

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Dec 27, 1971
Accession Number
AD0745875

Entities

People

  • Alan W. Mcmasters

Organizations

  • Naval Postgraduate School

Tags

Communities of Interest

  • Air Platforms

DTIC Thesaurus Topics

  • Abstracts
  • Algorithms
  • Applied Mathematics
  • California
  • Computations
  • Computer Programming
  • Construction
  • Equations
  • Flow Network
  • Graph Theory
  • Graphs
  • Linear Programming
  • Mathematics
  • Operations Research
  • Two Dimensional
  • United States

Readers

  • Graph Algorithms and Convex Optimization.