| Article ID: | iaor20052751 |
| Country: | France |
| Volume: | 37 |
| Issue: | 3 |
| Start Page Number: | 179 |
| End Page Number: | 194 |
| Publication Date: | Jul 2003 |
| Journal: | RAIRO Operations Research |
| Authors: | Burkard Rainer E., Chen Guangting |
| Keywords: | Steiner problem |
In this paper, we study the problem of computing a minimum cost Steiner tree subject to a weight constraint in a Halin graph (a Halin graph consists of a tree whose nodes do not have degree 2, with all leaves connected in the plane to form a cycle) where each edge has a non-negative integer cost and a non-negative integer weight. We prove the NP-hardness of this problem and present a fully polynomial time approximation scheme for this NP-hard problem.