On dyadic fractional packings of T-joins
Abdi, Ahmad
; Cornuéjols, Gérard P.; and Palion, Zuzanna
(2022)
On dyadic fractional packings of T-joins
SIAM Journal on Discrete Mathematics, 36 (3).
2445 - 2451.
ISSN 0895-4801
; Cornuéjols, Gérard P.; and Palion, Zuzanna
(2022)
On dyadic fractional packings of T-joins
SIAM Journal on Discrete Mathematics, 36 (3).
2445 - 2451.
ISSN 0895-4801
Let G = (V,E) be a graph, and T ⊆ V a nonempty subset of even cardinality. The famous theorem of Edmonds and Johnson on the T-join polyhedron implies that the minimum cardinality of a T-cut is equal to the maximum value of a fractional packing of T-joins. In this paper, we prove that the fractions assigned may be picked as dyadic rationals, i.e. of the form a 2k for some integers a, k ≥ 0.
-
picture_as_pdf -
subject - Accepted Version
-
- Available under Creative Commons: Attribution 4.0
Downloads