| Title:
|
A bound for the Steiner tree problem in graphs (English) |
| Author:
|
Plesník, Ján |
| Language:
|
English |
| Journal:
|
Mathematica Slovaca |
| ISSN:
|
0139-9918 |
| Volume:
|
31 |
| Issue:
|
2 |
| Year:
|
1981 |
| Pages:
|
155-163 |
| . |
| Category:
|
math |
| . |
| MSC:
|
05C05 |
| MSC:
|
68R10 |
| idZBL:
|
Zbl 0458.05027 |
| idMR:
|
MR611627 |
| . |
| Date available:
|
2009-09-25T09:13:27Z |
| Last updated:
|
2012-07-31 |
| Stable URL:
|
http://hdl.handle.net/10338.dmlcz/128936 |
| . |
| Reference:
|
[1| AHO A. V., GAREY M. R., HWANG F. K: Rectilinear Steiner trees: Efficient special case algorithms.Networks 7, 1977, 37-58. Zbl 0351.05102, MR 0464663 |
| Reference:
|
[2] BERGE C.: Graphs and hypergraphs.North-Holland, Amsterdam 1973. Zbl 0254.05101, MR 0357172 |
| Reference:
|
[3] BORŮVKA O.: O jistém problému minimálním.Práce moravské přírodovědecké společnosti 3, 1926, 37-58. |
| Reference:
|
[4] CHRISTOFIDES N.: Graph theory - An algorithmic approach.Academic Press, London 1975. Zbl 0321.94011, MR 0429612 |
| Reference:
|
[5] CHRISTOFIDES N.: Worst-case analysis of a new heuristic for the traveling salesman problem.Math. Programming, to appear. |
| Reference:
|
[6] CHUNG F. R. K., GILBERT E. N.: Steiner trees for the regular simplex.Bull. Inst. Math. Acad. Sinica 4, 1976, 313-325. Zbl 0351.05103, MR 0505711 |
| Reference:
|
[7] CHUNG F. R. K., HWANG F. K.: A lower bound for the Steiner tree problem.SIAM J. appl. Math. 34, 1978, 27-36. Zbl 0376.05020, MR 0482833 |
| Reference:
|
[8] ČULÍK K., DOLEŽAL V., FIEDLER M.: Kombinatorická analýza v praxi.SNTL - Nakladatelstvi technicke literatury, Praha 1967. |
| Reference:
|
[9] DREYFUS S. E., WAGNER R. A.: The Steiner problem in graphs.Networks 1, 1971, 194-207. MR 0297107 |
| Reference:
|
[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. Zbl 0399.05023, MR 0443427 |
| Reference:
|
[11] GAREY M. R., JOHNSON D. S.: The rectilinear Steiner tree problem is NP-complete.SIAM J. Appl. Math. 32, 1977, 826-834. Zbl 0396.05009, MR 0443426 |
| Reference:
|
[12] GILBERT E. N., POLLAK H. O.: Steiner minimal trees.SIAM J. Appl. Math. 16, 1968, 1-29. Zbl 0159.22001, MR 0223269 |
| Reference:
|
[13] GRAHAM R. L., HWANG F. K.: Remarks on Steiner minimal trees I.Bull. Inst. Math. Acad. Sinica 4, 1976, 177-182. MR 0437371 |
| Reference:
|
[14] HAKIMI S.L.: Steiner's problem in graphs and its implications.Networks 1, 1971, 113-133. Zbl 0229.05124, MR 0295947 |
| Reference:
|
[15] HANAN M.: On Steiner's problem with rectilinear distance.SIAM J. Appl. Math. 14, 1966, 255-265. Zbl 0151.33205, MR 0224500 |
| Reference:
|
[16] HWANG F. K.: On Steiner minimal trees with rectilinear distance.SIAM J. Appl. Math. 30, 1976, 104-114. Zbl 0322.05101, MR 0389632 |
| Reference:
|
[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 1829832 |
| Reference:
|
[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 0378476 |
| Reference:
|
[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. Zbl 0364.90104, MR 0459617 |
| Reference:
|
[20] TARJAN R. E.: Depth-first search and linear graph algorithms.SIAM J. Computing 1, 1972, 146-160. Zbl 0251.05107, MR 0304178 |
| . |
