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.

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

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.