National Technical Reports Library

The National Technical Information Service acquires, indexes, abstracts, and archives the largest collection of U.S. government-sponsored technical reports in existence. The NTRL offers online, free and open access to these authenticated government technical reports. Technical reports and documents in its repository may be available online for free either from the issuing federal agency, the U.S. Government Publishing Office’s Federal Digital System website, or through search engines.

Details

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

ADA448106

Publication Date	1988
Personal Author	Bixby, R. E.; Rajan, A.
Page Count	17
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.
Keywords	Matrices(Mathematics) Combinatorial analysis Decomposition Theorems Network flows Graphs Matrices(Circuits) Linear programming Ranking Reduction Separation Operations research Truemper-tseng theorem Max-flow min-cut matroids Binary representations Partial representations Submatrices Induced separations Series-parallel reductions Rank functions Series reductions Parallel reductions Coloops Isomorphisms Mathematical proofs Combinatorial theory
Source Agency	Non Paid ADAS
Corporate Authors	Rice Univ., Houston, TX. Dept. of Computational and Applied Mathematics.
Supplemental Notes	Prepared in cooperation with AT&T Bell Laboratories.
Document Type	Technical Report
Title Note	Research paper.
NTIS Issue Number	200625
Contract Number	AFOSR-87-0276 NSF-DCR-8519204

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

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

Publication Date	1988
Personal Author	Bixby, R. E.; Rajan, A.
Page Count	17
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.
Keywords	Matrices(Mathematics) Combinatorial analysis Decomposition Theorems Network flows Graphs Matrices(Circuits) Linear programming Ranking Reduction Separation Operations research Truemper-tseng theorem Max-flow min-cut matroids Binary representations Partial representations Submatrices Induced separations Series-parallel reductions Rank functions Series reductions Parallel reductions Coloops Isomorphisms Mathematical proofs Combinatorial theory
Source Agency	Non Paid ADAS
Corporate Authors	Rice Univ., Houston, TX. Dept. of Computational and Applied Mathematics.
Supplemental Notes	Prepared in cooperation with AT&T Bell Laboratories.
Document Type	Technical Report
Title Note	Research paper.
NTIS Issue Number	200625
Contract Number	AFOSR-87-0276 NSF-DCR-8519204