Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
421006 | Discrete Applied Mathematics | 2006 | 8 Pages |
Abstract
The group Steiner tree problem consists of, given a graph G , a collection RR of subsets of V(G)V(G) and a cost c(e)c(e) for each edge of G , finding a minimum-cost subtree that connects at least one vertex from each R∈RR∈R. It is a generalization of the well-known Steiner tree problem that arises naturally in the design of VLSI chips. In this paper, we study a polyhedron associated with this problem and some extended formulations. We give facet defining inequalities and explore the relationship between the group Steiner tree problem and other combinatorial optimization problems.
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
Carlos E. Ferreira, Fernando M. de Oliveira Filho,