A nearly best-possible approximation algorithm for node-weighted Steiner trees. (English) Zbl 0836.68046

Klein, Philip; Ravi, R.

J. Algorithms 19, No. 1, 104-115 (1995).

Summary: We give the first approximation algorithm for the node-weighted Steiner tree problem. Its performance guarantee is within a constant factor of the best possible unless \(\widetilde {P} \supseteq NP\). \((\widetilde {P}\) stands for the complexity class deterministic quasi-polynomial time, or DTIME\([n^{\text{polylog }n}].)\) Our algorithm generalizes to handle other network-design problems.

MSC:

68W10	Parallel algorithms in computer science
68R10	Graph theory (including graph drawing) in computer science

Keywords:

node-weighted Steiner tree problem