A Short Proof of the Truemper-Tseng Theorem on Max-Flow Min-Cut Matroids

Abstract

P. D. Seymour has characterized the matroids satisfying the integral max-flow min-cut property with respect to a fixed element. K. Truemper and F. T. Tseng subsequently proved a decomposition theorem for this class, similar in spirit to K. Wagner's characterization of the graphs containing no K(sub 5) minor and Seymour's characterization of the regular (totally unimodular) matroids. The purpose of this paper is to give a short, self-contained exposition of the Truemper-Tseng result.

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Jun 03, 1988
Accession Number
ADA448106

Entities

People

  • Arvind Rajan
  • Robert E. Bixby

Organizations

  • Rice University

Tags

DTIC Thesaurus Topics

  • Abstracts
  • Applied Mathematics
  • Availability
  • Classification
  • Contracts
  • Cooperation
  • Decomposition
  • Information Operations
  • Instructions
  • Integrals
  • Mathematics
  • Monitoring
  • Security
  • Standards

Readers

  • Analytical Mechanics
  • Graph Algorithms and Convex Optimization.