NDLI: A Graph Reduction Step Preserving Element-Connectivity and Packing Steiner Trees and Forests

Content Provider	Society for Industrial and Applied Mathematics (SIAM)
Author	Chekuri, Chandra Korula, Nitish
Copyright Year	2014
Abstract	Given an undirected graph $G=(V,E)$ and a subset of vertices called terminals $T \subseteq V$, the element-connectivity $\elconn_G(u,v)$ of two terminals $u,v \in T$ is the maximum number of $u$-$v$ paths that are pairwise element-disjoint, that is, disjoint in both edges and nonterminals $V \setminus T$. (Element-connectivity 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 [\em 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, \ldots, 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(\frac{k}{\log \|T\| \log h})$ element-disjoint Steiner forests, where $T = \bigcup_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.
Starting Page	577
Ending Page	597
Page Count	21
File Format	PDF
ISSN	08954801
DOI	10.1137/120882147
e-ISSN	10957146
Journal	SIAM Journal on Discrete Mathematics (SJDMEC)
Issue Number	2
Volume Number	28
Language	English
Publisher	Society for Industrial and Applied Mathematics
Publisher Date	2014-04-08
Access Restriction	Subscribed
Subject Keyword	Steiner trees element-disjoint packing Steiner trees and forests Factorization, matching, partitioning, covering and packing element-connectivity Steiner forests Connectivity Graph theory Graph algorithms Combinatorial optimization
Content Type	Text
Resource Type	Article
Subject	Mathematics

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in

An Approximate Max-Steiner-Tree-Packing Min-Steiner-Cut Theorem*

Covering, Packing and Generalized Perfection

Covering a Graph by Forests and a Matching

Disjoint Paths in a Planar GraphA General Theorem

On Extremal Graphs with at Most $$\ell $$ Internally Disjoint Steiner Trees Connecting Any $$n-1$$ Vertices

The Minimum All-Ones Problem for Trees

Bipartite Edge Coloring in $O(\Delta m)$ Time

Spanning Rigid Subgraph Packing and Sparse Subgraph Covering

Optimal Matching Forests and Valuated Delta-Matroids

A Graph Reduction Step Preserving Element-Connectivity and Packing Steiner Trees and Forests

Similar Documents

An Approximate Max-Steiner-Tree-Packing Min-Steiner-Cut Theorem*

Covering, Packing and Generalized Perfection

Covering a Graph by Forests and a Matching

Disjoint Paths in a Planar GraphA General Theorem

On Extremal Graphs with at Most $$\ell $$ Internally Disjoint Steiner Trees Connecting Any $$n-1$$ Vertices

The Minimum All-Ones Problem for Trees

Bipartite Edge Coloring in $O(\Delta m)$ Time

Spanning Rigid Subgraph Packing and Sparse Subgraph Covering

Optimal Matching Forests and Valuated Delta-Matroids

A Graph Reduction Step Preserving Element-Connectivity and Packing Steiner Trees and Forests