A Field Guide to Identifying Network Flow and Matching Problems.

reportActive / Technical Report | Accession Number: ADA047027 | Open PDF

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

Author(s):
Bartholdi, John J., Iii ; Ratliff, H. Donald
Author Organization(s):
FLORIDA UNIV GAINESVILLE DEPT OF INDUSTRIAL AND SYSTEMS ENGINEERING
Descriptive Note:
Research rept.,
Pagination:
0038

Security Markings

DOCUMENT & CONTEXTUAL SUMMARY

Distribution:
Approved For Public Release

RECORD

Collection: TR
Identifying Numbers
Report Number(s):
RR-77-12
Contract/Grant Number(s):
N00014-76-C-0096
Project Number(s):
2O061102A14D
 Subject Terms
Joint Capability Areas:
JCA_6.1_Information Transport; JCA_6_Net Centric; JCA_1.2_Force Preparation; JCA_1_Force Support; JCA_1.2.3_Educating; JCA_4.6_Engineering
Communities of Interest:
No COI(s) Identified
Descriptor(s):
*INTEGER PROGRAMMING, *NETWORK FLOWS, ALGORITHMS, MATRICES(MATHEMATICS), NAVAL RESEARCH, MATCHING
Field(s)/Group(s):
Theoretical Mathematics
Keyword(s):
AS14D, PE61102A
Report Date:
1977 Sep 01