History


Please fill in your query. A complete syntax description you will find on the General Help page.
The Schrijver system of odd join polyhedra. (English)
Combinatorica 8, No.1, 103-116 (1988).
Graphs for which the set of t-joins and t-cuts has “the max-flow-min-cut property”, i.e. for which the minimal defining system of the t-join polyhedron is totally dual integral, have been characterized by {\it P. D. Seymour} [J. Comb. Theory, Ser. B 23, 189-222 (1977; Zbl 0375.05022)]. An extension of this problem is to characterize the (uniquely existing) minimal totally dual integral defining system (Schrijver-system, discussed by {\it A. Schrijver} [Linear Algebra Appl. 38, 27-32 (1981; Zbl 0474.90065)]) of an arbitrary t-join polyhedron. This problem is solved in the present paper. The main idea is to use t-borders, a generalization of t-cuts, to obtain an integer minimax formula for the cardinality of a minimum t-join. (A t-border is the set of edges joining different classes of a partition of the vertex set into t-odd sets.) It turns out that the (uniquely existing) “strongest minimax theorem” involves just this notion.
WorldCat.org
Valid XHTML 1.0 Transitional Valid CSS!