Two-Trees Optimal T-Join and Integral Packing of T-Cuts

✍ Scribed by E. Korach

• Publisher: Elsevier Science
• Year: 1994
• Tongue: English
• Weight: 387 KB
• Volume: 62
• Category: Article
• ISSN: 0095-8956
• DOI: 10.1006/jctb.1994.1051

✦ Synopsis

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 theorem of (\mathrm{P}). Seymour on packing of (T)-cuts and a theorem of A. Frank on planar edge disjoint paths. It also solves positively a conjecture by A. Frank. The proof of the main theorem implies a polynomial algorithm for optimal integral packing of (T)-cuts for the case where the optimal (T)-join consists of two trees. This algorithm is in fact a simple post-optimality method that can be applied to existing algorithms for (\frac{1}{2}) integral packing of (T)-cuts and also solves polynomially a certain planar integral multicommodity flow problem. 1994 Academic Press, Inc.