Next: Polymatroid Steiner Problem
Up: Steiner Tree Problems
Previous: Shallow-Light -Steiner Tree
, set of terminals
, steiner nodes
, the edge weights
, cost function
- COST FUNCTION:
Approximable with 5.16 and 5 .
Includes the Metric Steiner Tree Problem as a special case,
hence it is NP-hard to approximate within an approximation ration 96/95 .
Special case where S and Y are disjoint is called the Steiner Tree Star Problem. This is already NP-hard .
2015-04-27 Revision: 288 PDF version