# Constrained Steiner trees in Halin graphs

Guangting Chen; Rainer E. Burkard

RAIRO - Operations Research (2010)

- 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 37.3 (2010): 179-194. <http://eudml.org/doc/105288>.

@article{Chen2010,

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},

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

language = {eng},

month = {3},

number = {3},

pages = {179-194},

publisher = {EDP Sciences},

title = {Constrained Steiner trees in Halin graphs},

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

volume = {37},

year = {2010},

}

TY - JOUR

AU - Chen, Guangting

AU - Burkard, Rainer E.

TI - Constrained Steiner trees in Halin graphs

JO - RAIRO - Operations Research

DA - 2010/3//

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/105288

ER -

## References

top- 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.
- 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.90006
- 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.68039
- R. Hassin, Approximation schemes for the restricted shortest path problem. Math. Oper. Res.17 (1992) 36-42. Zbl0763.90083
- F.K. Hwang and D.S. Richards, Steiner tree problems. Networks22 (1992) 55-89. Zbl0749.90082
- F.K. Hwang, D.S. Richards and P. Winter, The Steiner tree problem. Ann. Discrete Math.53 (1992) 68-71. Zbl0774.05001
- 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.
- 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.90057
- P. Winter, Steiner problem in Halin networks. Discrete Appl. Math.17 (1987) 281-294 . Zbl0623.94024
- P. Winter, Steiner problem in networks - a survey. Networks17 (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.