On the Clustered Steiner Tree Problem

摘要

We investigate the Clustered Steiner tree problem on metric graphs, which is a variant of Steiner minimum tree problem. The required vertices are partitioned into clusters, and in a feasible clustered Steiner tree, the subtrees spanning two different clusters must be disjoint. In this paper, we show that the problem remains NP-hard even if the topologies of all clusters and the inter-cluster tree are given. We propose a (ρ+2)-approximation algorithm for the general case, in which ρ is the approximation ratio for the Steiner tree problem. When the topologies for all clusters are given, we show a (ρ + 1)-approximation algorithm. We also discuss the Steiner ratio for this problem. We show the ratio is lower and upper bounded by three and four, respectively.