# Constrained Steiner trees in Halin graphs

Guangting Chen; Rainer E. Burkard

RAIRO - Operations Research - Recherche Opérationnelle (2003)

- Volume: 37, Issue: 3, page 179-194
- ISSN: 0399-0559

## Access Full Article

top## Abstract

top## How to cite

topChen, Guangting, and Burkard, Rainer E.. "Constrained Steiner trees in Halin graphs." RAIRO - Operations Research - Recherche Opérationnelle 37.3 (2003): 179-194. <http://eudml.org/doc/245124>.

@article{Chen2003,

abstract = {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.},

author = {Chen, Guangting, Burkard, Rainer E.},

journal = {RAIRO - Operations Research - Recherche Opérationnelle},

keywords = {Steiner trees; Halin graph; approximation scheme},

language = {eng},

number = {3},

pages = {179-194},

publisher = {EDP-Sciences},

title = {Constrained Steiner trees in Halin graphs},

url = {http://eudml.org/doc/245124},

volume = {37},

year = {2003},

}

TY - JOUR

AU - Chen, Guangting

AU - Burkard, Rainer E.

TI - Constrained Steiner trees in Halin graphs

JO - RAIRO - Operations Research - Recherche Opérationnelle

PY - 2003

PB - EDP-Sciences

VL - 37

IS - 3

SP - 179

EP - 194

AB - 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.

LA - eng

KW - Steiner trees; Halin graph; approximation scheme

UR - http://eudml.org/doc/245124

ER -

## References

top- [1] G. Chen and G. Xue, A PTAS for weight constrained Steiner trees in series-parallel graphs. Springer-verlag, Lecture Notes in Comput. Sci. 2108 (2001) 519-528. Zbl0991.68743MR1935889
- [2] G. Chen and G. Xue, K-pair delay constrained minimum cost routing in undirected networks. Proc. of the 13th Annual ACM-SIAM Symposium on Discrete Algorithms (2001) 230-231. Zbl1018.90006MR1958413
- [3] M.R. Garey and D.S. Johnson, Computers and Intractability: A Guide to the Theory of P-Completeness. San Francisco, W.H. Freeman and Company (1979). Zbl0411.68039MR519066
- [4] R. Hassin, Approximation schemes for the restricted shortest path problem. Math. Oper. Res. 17 (1992) 36-42. Zbl0763.90083MR1148776
- [5] F.K. Hwang and D.S. Richards, Steiner tree problems. Networks 22 (1992) 55-89. Zbl0749.90082MR1140372
- [6] F.K. Hwang, D.S. Richards and P. Winter, The Steiner tree problem. Ann. Discrete Math. 53 (1992) 68-71. Zbl0774.05001MR1192785
- [7] T. Jiang and L. Wang, Computing shortest networks under a fixed topology, in Advances in Steiner Trees, edited by D.-Z. Du, J.M. Smith and J. H. Rubinstein. Kluwer Academic Publishers (2000) 39-62. Zbl0947.68117MR1758347
- [8] D.H. Lorenz and D. Raz, A simple efficient approximation scheme for the restricted shortest path problem. Oper. Res. Lett. 28 (2001) 213-219. Zbl0992.90057MR1845768
- [9] P. Winter, Steiner problem in Halin networks. Discrete Appl. Math. 17 (1987) 281-294. Zbl0623.94024MR890638
- [10] P. Winter, Steiner problem in networks – a survey. Networks 17 (1987) 129-167. Zbl0646.90028

## NotesEmbed ?

topTo embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.