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
topHow 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.
- 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).
- R. Hassin, Approximation schemes for the restricted shortest path problem. Math. Oper. Res.17 (1992) 36-42.
- F.K. Hwang and D.S. Richards, Steiner tree problems. Networks22 (1992) 55-89.
- F.K. Hwang, D.S. Richards and P. Winter, The Steiner tree problem. Ann. Discrete Math.53 (1992) 68-71.
- 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 .
- P. Winter, Steiner problem in Halin networks. Discrete Appl. Math.17 (1987) 281-294 .
- P. Winter, Steiner problem in networks - a survey. Networks17 (1987) 129-167.
NotesEmbed ?
topYou must be logged in to post comments.
To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.