A Field Guide to Identifying Network Flow and Matching Problems.

Abstract

In an important but apparently little-known result, M. Iri has given necessary and sufficient conditions for a linear program to be solvable as a network flow problem. For tutorial purposes we recapitulate his result, though from a different perspective. Then in the same spirit we characterize linear programs that are solvable by the matching algorithm. (Author)

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Sep 01, 1977
Accession Number
ADA047027

Entities

People

  • H. Donald Ratliff
  • John J. Bartholdi Iii

Organizations

  • University of Florida

Tags

DTIC Thesaurus Topics

  • Algorithms
  • Camouflage
  • Convex Programming
  • Electrical Engineering
  • Engineering
  • Evolutionary Algorithms
  • Heuristic Methods
  • Integer Programming
  • Linear Programming
  • Mathematical Programming
  • Military Research
  • New York
  • Operations Research
  • Systems Engineering
  • Terminals

Fields of Study

  • Computer science

Readers

  • Applied Combinatorial Optimization and Logic Circuit Design.
  • Fluid Dynamics.
  • Systems Analysis and Design