## Abstract

Given an undirected graph G = (V,E) and a subset of vertices called terminals T ⊆ V , the element-connectivity k_{G}(u, v) of two terminals u, v ∈ 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 T1, T2, . . . , Th, we seek a maximum number of element-disjoint Steiner forests where each forest connects each Ti. We prove that if each Ti is k-element-connected, then there exist ω( k/log |T| 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 ω(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.

Original language | English (US) |
---|---|

Pages (from-to) | 577-597 |

Number of pages | 21 |

Journal | SIAM Journal on Discrete Mathematics |

Volume | 28 |

Issue number | 2 |

DOIs | |

State | Published - 2014 |

## Keywords

- Element-connectivity
- Element-disjoint
- Packing Steiner trees and forests
- Steiner forests
- Steiner trees

## ASJC Scopus subject areas

- General Mathematics