Next: Prize-Collecting k-Bottleneck Steiner Tree
Up: Steiner Tree Problems
Previous: k-Bottleneck Steiner Tree Problem
, edge costs
, set of terminals
, a penalty function
- COST FUNCTION:
Can be solved exactly in polynomial time .
This entry covers the penalty-based variant of the Prize-Collecting Steiner Tree Problem. The quota-based Prize-Collecting Steiner Tree Problem, as well as the related Steiner Forest problems can also be solved in polynomial time .
2015-04-27 Revision: 288 PDF version