Constrained Steiner trees in Halin graphs
The School of Science,
Hangzhou Institute of Electronics Engineering, Hangzhou 310037,
P.R. China; firstname.lastname@example.org.
2 Technische Universität Graz, Institut für Mathematik, Steyrergasse 30, A-8010 Graz, Austria; email@example.com.
In this paper, we study the problem of computing a minimum cost Steiner tree subject to a weight constraint in a Halin graph where each edge has a nonnegative integer cost and a nonnegative integer weight. We prove the NP-hardness of this problem and present a fully polynomial time approximation scheme for this NP-hard problem.
Key words: Steiner trees / Halin graph / approximation scheme.
© EDP Sciences, 2003