论文标题
聚集的选定内部施盐树问题
The clustered selected-internal Steiner tree problem
论文作者
论文摘要
Given a complete graph $G=(V,E)$, with nonnegative edge costs, two subsets $R \subset V$ and $R^{\prime} \subset R$, a partition $\mathcal{R}=\{R_1,R_2,\ldots,R_k\}$ of $R$, $R_i \cap R_j=ϕ$, $i \neq J $和$ \ Mathcal {r}^{\ prime} = \ {r^{\ prime} _1，r^{\ prime} _2，\ ldots，r^{\ prime} _k \ \} $是$ r $ $ r $的所有顶点的树$ t $ t $ t $，可以将$ t $切成$ k $ subtrees $ t_i $，通过删除$ k-1 $ edges和每个子树$ t_i $跨越$ r_i $，$ r_i $，$ 1 \ leq i \ leq i \ leq k $。簇状的坦纳树的成本被定义为其所有边缘成本的总和。如果$ r^{\ prime} _i $中的所有顶点是$ t_i $，$ t_i $，$ 1 \ leq I \ leq leq k $，则$ g $的群集选择内施坦树是$ r $的簇状的施泰纳树。群集的选定内部施坦纳树问题与确定$ r $ $ r $的聚类 - 内部施泰纳树$ t $，$ r $ in $ g $，最低成本。在本文中，我们介绍了第一个已知的近似值算法，其性能比（ρ+4）$用于群集选定的内部steiner树问题，其中$ρ$是Steiner树问题的最著名的性能比率。
Given a complete graph $G=(V,E)$, with nonnegative edge costs, two subsets $R \subset V$ and $R^{\prime} \subset R$, a partition $\mathcal{R}=\{R_1,R_2,\ldots,R_k\}$ of $R$, $R_i \cap R_j=ϕ$, $i \neq j$ and $\mathcal{R}^{\prime}=\{R^{\prime}_1,R^{\prime}_2,\ldots,R^{\prime}_k\}$ of $R^{\prime}$, $R^{\prime}_i \subset R_i$, a clustered Steiner tree is a tree $T$ of $G$ that spans all vertices in $R$ such that $T$ can be cut into $k$ subtrees $T_i$ by removing $k-1$ edges and each subtree $T_i$ spanning all vertices in $R_i$, $1 \leq i \leq k$. The cost of a clustered Steiner tree is defined to be the sum of the costs of all its edges. A clustered selected-internal Steiner tree of $G$ is a clustered Steiner tree for $R$ if all vertices in $R^{\prime}_i$ are internal vertices of $T_i$, $1 \leq i \leq k$. The clustered selected-internal Steiner tree problem is concerned with the determination of a clustered selected-internal Steiner tree $T$ for $R$ and $R^{\prime}$ in $G$ with minimum cost. In this paper, we present the first known approximation algorithm with performance ratio $(ρ+4)$ for the clustered selected-internal Steiner tree problem, where $ρ$ is the best-known performance ratio for the Steiner tree problem.
