Next: Directed Steiner Tree Problem
Up: Steiner Tree Problems
Previous: Steiner Tree Problems
, edge costs
, set of terminals
in G such that
- COST FUNCTION:
 (see also ,).
NP-hard to approximate within an approximation ratio 96/95 .
Admits a PTAS in the special case when G is a planar graph .
Solvable exactly in time
is the number of vertices,
the number of terminals
the number of edges in the graph ,.
2015-04-27 Revision: 288 PDF version