𝔖 Bobbio Scriptorium
✦   LIBER   ✦

On the integral 4-packing of T-cuts

✍ Scribed by Frieda Granot; Michal Penn

Publisher
Elsevier Science
Year
1995
Tongue
English
Weight
777 KB
Volume
142
Category
Article
ISSN
0012-365X

No coin nor oath required. For personal study only.

✦ Synopsis

Let C = (V, E) be an undirected graph, w : E + Z' a weight function and T c V an even subset of vertices from G. A T-cut is an edge-cut set which divides T into two odd sets. For ( Tj = 4 Seymour gave a good characterization of the graphs for which there exists a maximum packing of T-cuts that is integral. Based on Seymour's characterization we provide a simple 0(n3m + PI"&) algorithm for increasing minimally the weight function on the edge-set of a graph so that the value of the maximum integral packing of T-cuts with respect to the increased weights is equal to the original value of a minimum weight T-join.

πŸ“œ SIMILAR VOLUMES

On Packing T-Cuts
On Packing T-Cuts
✍ A. Frank; Z. Szigeti πŸ“‚ Article πŸ“… 1994 πŸ› Elsevier Science 🌐 English βš– 355 KB

Notes On Packing \(T\)-Cuts* AndrΓ‘s Frank \({ }^{\dagger}\) Research Institute for Discrete Mathematics, University of Bonn, Nassestr. 2, Bonn-1, Germany, D-5300 Received July 2, 1992 A short proof of a difficult theorem of P. D. Seymour on grafts with the max-flow

Two-Trees Optimal T-Join and Integral Pa
Two-Trees Optimal T-Join and Integral Packing of T-Cuts
✍ E. Korach πŸ“‚ Article πŸ“… 1994 πŸ› Elsevier Science 🌐 English βš– 387 KB

Let \(G\) be an undirected graph, \(T\) an even subset of vertices and \(F\) an optimal \(T\)-join, which is a forest of two trees. The main theorem of this paper characterizes the cases, where \((G, T)\) has an optimal packing of \(T\)-cuts which is integral. This theorem unifies and generalizes a

On the Cuts of Scattering Amplitudes
On the Cuts of Scattering Amplitudes
✍ Pierpaolo Mastrolia πŸ“‚ Article πŸ“… 2008 πŸ› Elsevier Science 🌐 English βš– 214 KB