PTAS for weight constrained Steiner trees in series-parallel graphs
In this paper, we study the problem of computing a minimum cost Steiner tree subject to weight constraint in a series-parallel graph where each edge has a nonnegative integer cost and a nonnegative integer weight. We present a strongly polynomial time approximation scheme for this NP-complete problem. (C) 2003 Published by Elsevier B.V.
steiner trees series-parallel graphs multiple constraints quality of service