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

Abstract

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

How to cite

top

Chen, 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. [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. [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. [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. [4] R. Hassin, Approximation schemes for the restricted shortest path problem. Math. Oper. Res. 17 (1992) 36-42. Zbl0763.90083MR1148776
  5. [5] F.K. Hwang and D.S. Richards, Steiner tree problems. Networks 22 (1992) 55-89. Zbl0749.90082MR1140372
  6. [6] F.K. Hwang, D.S. Richards and P. Winter, The Steiner tree problem. Ann. Discrete Math. 53 (1992) 68-71. Zbl0774.05001MR1192785
  7. [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. [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. [9] P. Winter, Steiner problem in Halin networks. Discrete Appl. Math. 17 (1987) 281-294. Zbl0623.94024MR890638
  10. [10] P. Winter, Steiner problem in networks – a survey. Networks 17 (1987) 129-167. Zbl0646.90028

NotesEmbed ?

top

You must be logged in to post comments.