Geodesic
A bound for the Steiner tree problem in graphs
Mathematica slovaca, Tome 31 (1981) no. 2, pp. 155-163
Cet article a éte moissonné depuis la source Czech Digital Mathematics Library

Voir la notice de l'article

Classification : 05C05, 68R10 
@article{MASLO_1981_31_2_a5,
     author = {Plesn{\'\i}k, J\'an},
     title = {A bound for the {Steiner} tree problem in graphs},
     journal = {Mathematica slovaca},
     pages = {155--163},
     year = {1981},
     volume = {31},
     number = {2},
     mrnumber = {611627},
     zbl = {0458.05027},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/MASLO_1981_31_2_a5/}
}
TY  - JOUR
AU  - Plesník, Ján
TI  - A bound for the Steiner tree problem in graphs
JO  - Mathematica slovaca
PY  - 1981
SP  - 155
EP  - 163
VL  - 31
IS  - 2
UR  - http://geodesic.mathdoc.fr/item/MASLO_1981_31_2_a5/
LA  - en
ID  - MASLO_1981_31_2_a5
ER  - 
%0 Journal Article
%A Plesník, Ján
%T A bound for the Steiner tree problem in graphs
%J Mathematica slovaca
%D 1981
%P 155-163
%V 31
%N 2
%U http://geodesic.mathdoc.fr/item/MASLO_1981_31_2_a5/
%G en
%F MASLO_1981_31_2_a5
Plesník, Ján. A bound for the Steiner tree problem in graphs. Mathematica slovaca, Tome 31 (1981) no. 2, pp. 155-163. http://geodesic.mathdoc.fr/item/MASLO_1981_31_2_a5/

[1| AHO A. V., GAREY M. R., HWANG F. K: Rectilinear Steiner trees: Efficient special case algorithms. Networks 7, 1977, 37-58. | MR | Zbl

[2] BERGE C.: Graphs and hypergraphs. North-Holland, Amsterdam 1973. | MR | Zbl

[3] BORŮVKA O.: O jistém problému minimálním. Práce moravské přírodovědecké společnosti 3, 1926, 37-58.

[4] CHRISTOFIDES N.: Graph theory - An algorithmic approach. Academic Press, London 1975. | MR | Zbl

[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. | MR | Zbl

[7] CHUNG F. R. K., HWANG F. K.: A lower bound for the Steiner tree problem. SIAM J. appl. Math. 34, 1978, 27-36. | MR | Zbl

[8] ČULÍK K., DOLEŽAL V., FIEDLER M.: Kombinatorická analýza v praxi. SNTL - Nakladatelstvi technicke literatury, Praha 1967.

[9] DREYFUS S. E., WAGNER R. A.: The Steiner problem in graphs. Networks 1, 1971, 194-207. | MR

[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. | MR | Zbl

[11] GAREY M. R., JOHNSON D. S.: The rectilinear Steiner tree problem is NP-complete. SIAM J. Appl. Math. 32, 1977, 826-834. | MR | Zbl

[12] GILBERT E. N., POLLAK H. O.: Steiner minimal trees. SIAM J. Appl. Math. 16, 1968, 1-29. | MR | Zbl

[13] GRAHAM R. L., HWANG F. K.: Remarks on Steiner minimal trees I. Bull. Inst. Math. Acad. Sinica 4, 1976, 177-182. | MR

[14] HAKIMI S.L.: Steiner's problem in graphs and its implications. Networks 1, 1971, 113-133. | MR | Zbl

[15] HANAN M.: On Steiner's problem with rectilinear distance. SIAM J. Appl. Math. 14, 1966, 255-265. | MR | Zbl

[16] HWANG F. K.: On Steiner minimal trees with rectilinear distance. SIAM J. Appl. Math. 30, 1976, 104-114. | MR | Zbl

[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. | MR

[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. | MR

[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. | MR | Zbl

[20] TARJAN R. E.: Depth-first search and linear graph algorithms. SIAM J. Computing 1, 1972, 146-160. | MR | Zbl