Accession Number:

AD0762466

Title:

Blocking Pairs of Polyhedra Arising from Network Flows

Descriptive Note:

Technical rept.

Corporate Author:

CORNELL UNIV ITHACA NY DEPT OF OPERATIONS RESEARCH

Report Date:

1973-06-01

Pagination or Media Count:

32.0

Abstract:

A study is made of blocking pairs of polyhedra blocking pairs of matrices that arise in or can be transformed into a network flow context. For example, the blocking polyhedron of the polyhedron generated by all integral feasible flows in a capacity-constrained supply-demand network where all the data are integral is explicitly determined, and a simple algorithm is described for solving the associated integral packing problem. Applications of these results to k-ways in directed graphs, 0,1-matrices with prescribed row and column sums, and to flow arborescences are described.

Subject Categories:

  • Operations Research

Distribution Statement:

APPROVED FOR PUBLIC RELEASE