Back to Search
Start Over
NEW REDUCTION TECHNIQUES FOR THE GROUP STEINER TREE PROBLEM.
- Source :
-
SIAM Journal on Optimization . 2006, Vol. 17 Issue 4, p1176-1188. 13p. 2 Charts, 3 Graphs. - Publication Year :
- 2006
-
Abstract
- The group Steiner tree problem consists of, given a graph G, a collection R of subsets of V (G), and a positive cost ce for each edge e of G, finding a minimum-cost tree in G that contains at least one vertex from each R ∈ R. We call the sets in R groups. The well-known Steiner tree problem is the special case of the group Steiner tree problem in which each set in R is unitary. In this paper, we present a general reduction test designed to remove group vertices, that is, vertices belonging to some group. Through the use of these tests we can conclude that a given group vertex can be considered a nonterminal and hence can be removed from its group. We also present some computational results on instances from SteinLib [T. Koch, A. Martin, and S. Voss, SteinLib: An updated library on Steiner tree problems in graphs, in Steiner Trees in Industry, Kluwer Academic Publishers, Dordrecht, The Netherlands, 2001, pp. 285-325]. [ABSTRACT FROM AUTHOR]
- Subjects :
- *STEINER systems
*UNITARY groups
*TREE graphs
*GRAPH theory
*MATHEMATICAL analysis
Subjects
Details
- Language :
- English
- ISSN :
- 10526234
- Volume :
- 17
- Issue :
- 4
- Database :
- Academic Search Index
- Journal :
- SIAM Journal on Optimization
- Publication Type :
- Academic Journal
- Accession number :
- 25175520
- Full Text :
- https://doi.org/10.1137/040610891