Premium
Approximation algorithm for the group Steiner network problem
Author(s) -
Penn Michal,
Rozenfeld Stas
Publication year - 2007
Publication title -
networks
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.977
H-Index - 64
eISSN - 1097-0037
pISSN - 0028-3045
DOI - 10.1002/net.20151
Subject(s) - steiner tree problem , combinatorics , mathematics , group (periodic table) , approximation algorithm , partition (number theory) , cardinality (data modeling) , vertex connectivity , generalization , steiner system , discrete mathematics , graph , algorithm , computer science , vertex (graph theory) , mathematical analysis , chemistry , organic chemistry , data mining
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 + 2 x ),2 I }, 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