Approximation algorithm for the group Steiner network problem
Michal Penn, Stas Rozenfeld · Networks · 2006
Abstract In this article we study the group Steiner network problem, which is defined in the following way. Given a graph G = (V,E), a partition of its vertices into K groups and connectivity requirements between the different groups, the aim is to find simultaneously a set of representatives, one for each group, and a minimum cost connected subgraph that satisfies the connectivity requirements between the groups (representatives). This problem is a generalization of the Steiner network problem and the group Steiner tree problem, two known NP‐complete problems. We present an approximation algorithm for a special case of the group Steiner network problem with an approximation ratio of min {2(1 + 2x),2I}, where I is the cardinality of the largest group and x is a parameter that depends on the cost function. © 2006 Wiley Periodicals, Inc. NETWORKS, Vol. 49(2), 160–167 2007