Next: Two-Level Rectilinear Steiner Tree
Up: Steiner Tree Problems
Previous: Stochastic Steiner Tree Problem
, edge cost
, and sets
, also called groups.
which contains at least one terminal from every group
- COST FUNCTION:
. Approximable within
is a tree
Not approximable within
unless NP admits quasipolynomial-time Las Vegas algorithm .
when the graph is planar and each group is the set of nodes on a face .
2015-04-27 Revision: 288 PDF version