We found a match
Your institution may have rights to this item. Sign in to continue.
- Title
Directed Steiner tree packing and directed tree connectivity.
- Authors
Sun, Yuefang; Yeo, Anders
- Abstract
For a digraph D=(V(D),A(D)) $D=(V(D),A(D))$, and a set S⊆V(D) $S\subseteq V(D)$ with r∈S $r\in S$ and ∣S∣≥2 $| S| \ge 2$, an (S,r) $(S,r)$‐tree is an out‐tree T $T$ rooted at r $r$ with S⊆V(T) $S\subseteq V(T)$. Two (S,r) $(S,r)$‐trees T1 ${T}_{1}$ and T2 ${T}_{2}$ are said to be arc‐disjoint if A(T1)∩A(T2)=∅ $A({T}_{1})\cap A({T}_{2})=\varnothing $. Two arc‐disjoint (S,r) $(S,r)$‐trees T1 ${T}_{1}$ and T2 ${T}_{2}$ are said to be internally disjoint if V(T1)∩V(T2)=S $V({T}_{1})\cap V({T}_{2})=S$. Let κS,r(D) ${\kappa }_{S,r}(D)$ and λS,r(D) ${\lambda }_{S,r}(D)$ be the maximum number of internally disjoint and arc‐disjoint (S,r) $(S,r)$‐trees in D $D$, respectively. The generalized k $k$‐vertex‐strong connectivity of D $D$ is defined as κk(D)=min{κS,r(D)∣S⊆V(D),∣S∣=k,r∈S}. ${\kappa }_{k}(D)=\min \{{\kappa }_{S,r}(D)| S\subseteq V(D),| S| \,=k,r\in S\}.$ Similarly, the generalized k $k$‐arc‐strong connectivity of D $D$ is defined as λk(D)=min{λS,r(D)∣S⊆V(D),∣S∣=k,r∈S}. ${\lambda }_{k}(D)=\min \{{\lambda }_{S,r}(D)| S\subseteq V(D),| S| \,=k,r\in S\}.$ The generalized k $k$‐vertex‐strong connectivity and generalized k $k$‐arc‐strong connectivity are also called directed tree connectivity which extends the well‐established tree connectivity on undirected graphs to directed graphs and could be seen as a generalization of classical connectivity of digraphs. In this paper, we completely determine the complexity for both κS,r(D) ${\kappa }_{S,r}(D)$ and λS,r(D) ${\lambda }_{S,r}(D)$ on general digraphs, symmetric digraphs, and Eulerian digraphs. In particular, among our results, we prove and use the NP‐completeness of 2‐linkage problem restricted to Eulerian digraphs. We also give sharp bounds and equalities for the two parameters κk(D) ${\kappa }_{k}(D)$ and λk(D) ${\lambda }_{k}(D)$.
- Subjects
DIRECTED graphs; EULERIAN graphs; GRAPH connectivity; UNDIRECTED graphs; TREES; NP-complete problems
- Publication
Journal of Graph Theory, 2023, Vol 102, Issue 1, p86
- ISSN
0364-9024
- Publication type
Article
- DOI
10.1002/jgt.22858