论文标题
定向坦者树包装和定向树连接
Directed Steiner tree packing and directed tree connectivity
论文作者
论文摘要
对于Digraph $ d =（v（d），a（d））$，$ s \ subseteq v（d）$带有$ r \ in s $ in s $和$ | s | \ geq 2 $，a $（s，r）$ - tree是$ r $ rug的$ r $ s $ s \ subseteq v（t）。如果$ a（t_1）\ cap a（t_2）= \ emptyset $，则两个$（s，r）$ - 树$ t_1 $和$ t_2 $。如果$ v（t_1）\ cap v（t_2）= s $，则两个Arc-disjoint $（S，R）$ - 树$ T_1 $和$ T_2 $在内部不相交。令$κ_{s，r}（d）$和$λ_{s，r}（d）$分别是内部分离的最大数量和arc-disjoint $（s，r）$ - $ d $中的树。 $ d $ $ d $的广义$ k $ -vertex-strong连接定义为$κ_k（d）= \ min \ {κ__{κ_{k {s，r}（d）\ mid s \ mid s \ subset v（d），| s | s | = k = k，in s \}。 $λ_k（d）= \ min \ {λ_{λ_{s，r}（d）\ mid s \ mid s \ subset v（d），| s | = k，r \ in s \}。$ $ $ $ $ $图形可以看作是挖掘的经典连通性的概括。 在本文中，我们完全确定了$κ__{s，r}（d）$和$λ_{s，r}（d）$的复杂性，对一般挖掘，对称挖掘和欧拉（Eulerian Digraphs）。特别是，在我们的结果中，我们证明并使用了仅限于Eulerian Digraphs的2-链接问题的NP完整性。我们还为两个参数$κ_K（d）$和$λ_K（d）$提供了尖锐的界限和特征。
For a digraph $D=(V(D), A(D))$, and a set $S\subseteq V(D)$ with $r\in S$ and $|S|\geq 2$, an $(S, r)$-tree is an out-tree $T$ rooted at $r$ with $S\subseteq V(T)$. Two $(S, r)$-trees $T_1$ and $T_2$ are said to be arc-disjoint if $A(T_1)\cap A(T_2)=\emptyset$. Two arc-disjoint $(S, r)$-trees $T_1$ and $T_2$ are said to be internally disjoint if $V(T_1)\cap V(T_2)=S$. Let $κ_{S,r}(D)$ and $λ_{S,r}(D)$ be the maximum number of internally disjoint and arc-disjoint $(S, r)$-trees in $D$, respectively. The generalized $k$-vertex-strong connectivity of $D$ is defined as $$κ_k(D)= \min \{κ_{S,r}(D)\mid S\subset V(D), |S|=k, r\in S\}.$$ Similarly, the generalized $k$-arc-strong connectivity of $D$ is defined as $$λ_k(D)= \min \{λ_{S,r}(D)\mid S\subset V(D), |S|=k, r\in S\}.$$ The generalized $k$-vertex-strong connectivity and generalized $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)$ and $λ_{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 characterizations for the two parameters $κ_k(D)$ and $λ_k(D)$.
