A bound for the Steiner tree problem in graphs

Ján Plesník

Mathematica Slovaca (1981)

  • Volume: 31, Issue: 2, page 155-163
  • ISSN: 0139-9918

How to cite

top

Plesník, Ján. "A bound for the Steiner tree problem in graphs." Mathematica Slovaca 31.2 (1981): 155-163. <http://eudml.org/doc/31674>.

@article{Plesník1981,
author = {Plesník, Ján},
journal = {Mathematica Slovaca},
keywords = {Steiner tree; Steiner minimal tree; polynomial algorithms; minimal spanning tree},
language = {eng},
number = {2},
pages = {155-163},
publisher = {Mathematical Institute of the Slovak Academy of Sciences},
title = {A bound for the Steiner tree problem in graphs},
url = {http://eudml.org/doc/31674},
volume = {31},
year = {1981},
}

TY - JOUR
AU - Plesník, Ján
TI - A bound for the Steiner tree problem in graphs
JO - Mathematica Slovaca
PY - 1981
PB - Mathematical Institute of the Slovak Academy of Sciences
VL - 31
IS - 2
SP - 155
EP - 163
LA - eng
KW - Steiner tree; Steiner minimal tree; polynomial algorithms; minimal spanning tree
UR - http://eudml.org/doc/31674
ER -

References

top
  1. [1| AHO A. V., GAREY M. R., HWANG F. K, Rectilinear Steiner trees: Efficient special case algorithms, Networks 7, 1977, 37-58. (1977) Zbl0351.05102MR0464663
  2. BERGE C., Graphs and hypergraphs, North-Holland, Amsterdam 1973. (1973) Zbl0254.05101MR0357172
  3. BORŮVKA O., O jistém problému minimálním, Práce moravské přírodovědecké společnosti 3, 1926, 37-58. (1926) 
  4. CHRISTOFIDES N., Graph theory - An algorithmic approach, Academic Press, London 1975. (1975) Zbl0321.94011MR0429612
  5. CHRISTOFIDES N., Worst-case analysis of a new heuristic for the traveling salesman problem, Math. Programming, to appear. 
  6. CHUNG F. R. K., GILBERT E. N., Steiner trees for the regular simplex, Bull. Inst. Math. Acad. Sinica 4, 1976, 313-325. (1976) Zbl0351.05103MR0505711
  7. CHUNG F. R. K., HWANG F. K., A lower bound for the Steiner tree problem, SIAM J. appl. Math. 34, 1978, 27-36. (1978) Zbl0376.05020MR0482833
  8. ČULÍK K., DOLEŽAL V., FIEDLER M., Kombinatorická analýza v praxi, SNTL - Nakladatelstvi technicke literatury, Praha 1967. (1967) 
  9. DREYFUS S. E., WAGNER R. A., The Steiner problem in graphs, Networks 1, 1971, 194-207. (1971) MR0297107
  10. GAREY M. R., GRAHAM R. L., JOHNSON D. S., The complexity of computing Steiner minimal trees, SIAM J. Appl. Math. 32, 1977, 835-859. (1977) Zbl0399.05023MR0443427
  11. GAREY M. R., JOHNSON D. S., The rectilinear Steiner tree problem is NP-complete, SIAM J. Appl. Math. 32, 1977, 826-834. (1977) Zbl0396.05009MR0443426
  12. GILBERT E. N., POLLAK H. O., Steiner minimal trees, SIAM J. Appl. Math. 16, 1968, 1-29. (1968) Zbl0159.22001MR0223269
  13. GRAHAM R. L., HWANG F. K., Remarks on Steiner minimal trees I, Bull. Inst. Math. Acad. Sinica 4, 1976, 177-182. (1976) MR0437371
  14. HAKIMI S.L., Steiner's problem in graphs and its implications, Networks 1, 1971, 113-133. (1971) Zbl0229.05124MR0295947
  15. HANAN M., On Steiner's problem with rectilinear distance, SIAM J. Appl. Math. 14, 1966, 255-265. (1966) Zbl0151.33205MR0224500
  16. HWANG F. K., On Steiner minimal trees with rectilinear distance, SIAM J. Appl. Math. 30, 1976, 104-114. (1976) Zbl0322.05101MR0389632
  17. JARNÍK V., KOSSLER M., O minimálních grafech obsahujicích n daných bodů, Časopis Pěst. Mat. Fys. 63, 1934, 223-235. (1934) MR1829832
  18. KARP R. M., Reducibility among combinatorial problems, In: Complexity of computer computations (R. E. Miller a and J. W. Thatcher, eds.) Plenum Press, New York 1972, 85-104. (1972) MR0378476
  19. ROSENKRANTZ D. J., STEARNS R. E., LEWIS P. M., An analysis of several heuristics for the traveling salesman problem, SIAM J. Comput. 6, 1977, 563-581. (1977) Zbl0364.90104MR0459617
  20. TARJAN R. E., Depth-first search and linear graph algorithms, SIAM J. Computing 1, 1972, 146-160. (1972) Zbl0251.05107MR0304178

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.