The clustered selected-internal Steiner tree problem

Abstract

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,\dots ,R_k\}$ of $R$, $R_i\cap R_j=\varphi$, $i\ne j$ and ${\mathcal{R}}^{\prime }=\{R_1^{\prime },R_2^{\prime },\dots ,R_k^{\prime }\}$ of $R^{\prime }$, $R_i^{\prime }\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\le i\le 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_i^{\prime }$ are internal vertices of $T_i$, $1\le i\le 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 $(\rho +4)$ for the clustered selected-internal Steiner tree problem, where $\rho$ is the best-known performance ratio for the Steiner tree problem.

I withdrawed this submitted (but not published) manuscript from Discrete Mathematics & Theoretical Computer Science (Journal) and "Theoretical Computer Science"(Journal), and then transferred to submit this Manuscript to "International Journal of Foundations of Computer Science", so i need to replace the manuscript by the form of International Journal of Foundations of Computer Science