A graph reduction step preserving element-connectivity and packing steiner trees and forests

Chandra Chekuri, Nitish Korula

Research output: Contribution to journalArticlepeer-review

Abstract

Given an undirected graph G = (V,E) and a subset of vertices called terminals T ⊆ V , the element-connectivity kG(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 = Ui Ti. 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 languageEnglish (US)
Pages (from-to)577-597
Number of pages21
JournalSIAM Journal on Discrete Mathematics
Volume28
Issue number2
DOIs
StatePublished - 2014

Keywords

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

ASJC Scopus subject areas

  • Mathematics(all)

Fingerprint Dive into the research topics of 'A graph reduction step preserving element-connectivity and packing steiner trees and forests'. Together they form a unique fingerprint.

Cite this