Blocking Pairs of Polyhedra Arising from Network Flows

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.

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Jun 01, 1973
Accession Number
AD0762466

Entities

People

  • D. R. Fulkerson
  • David B. Weinberger

Organizations

  • Cornell University

Tags

DTIC Thesaurus Topics

  • Algorithms
  • Applied Mathematics
  • Engineering
  • Flow Network
  • Graphs
  • Inequalities
  • Integrals
  • Mathematics
  • Military Research
  • New York
  • Operations Research
  • Three Dimensional
  • Two Dimensional
  • Universities

Readers

  • Graph Algorithms and Convex Optimization.
  • Linear Algebra
  • Operations Research