A GRAPH REDUCTION STEP PRESERVING ELEMENT-CONNECTIVITY AND PACKING STEINER TREES AND FORESTS

作者：Chekuri Chandra^*; Korula Nitish

来源：SIAM Journal on Discrete Mathematics, 2014, 28(2): 577-597.

DOI：10.1137/120882147

• element-connectivity
• Steiner trees
• Steiner forests
• element-disjoint
• packing Steiner trees and forests

Given an undirected graph G = (V, E) and a subset of vertices called terminals T subset of V, the element-connectivity kappa G' (u, v) of two terminals u, v is an element of T is the maximum number of u-v paths that are pairwise element-disjoint, that is, disjoint in both edges and nonterminals V \ T. (Elementconnectivity was first (implicitly) defined by Frank, Ibaraki, and Nagamochi in [J. Graph Theory, 17 (1993), pp. 275-281].) (Element-disjoint paths need not be disjoint in terminals.) Hind and Oellermann [Congr. Numer., 113 (1996), pp. 179-204] gave a graph reduction step that preserves the global element-connectivity of the terminals. We show that one can also apply such a reduction step while preserving local connectivity, that is, all the pairwise element-connectivities of the terminals. We illustrate the usefulness of this more general reduction step by giving applications to packing element-disjoint Steiner trees and forests: Given a graph G and disjoint terminal sets T-1, T-2,..., T-h, we seek a maximum number of element-disjoint Steiner forests where each forest connects each T-i. We prove that if each T-i is k-element-connected, then there exist Omega(k/LOG vertical bar T vertical bar log h) element-disjoint Steiner forests, where T = U-i T-i. If G is planar (or has fixed genus), we show that there exist Omega(k) Steiner forests. Our proofs are constructive, giving poly-time algorithms to find these forests; these are the first nontrivial algorithms for packing element-disjoint Steiner forests.

• 出版日期2014