STEINER PROBLEMS IN GRAPHS: ALGORITHMS AND APPLICATIONS

REFERENCES

• A. V. Aho , M. R. Garey , and F. K. Hwang , “ Rectilinear Steiner trees Efficient special case algorithms ,” Networks , 7 , 37 – 58 ( 1977 ).
   Web of Science ®Google Scholar
• E. R. Berlekamp , Private Communication cited in Computers and Intractability A Guide to the Theory of N P-completeness by M. R. Garey, D. S. Johnson, W. H. Freeman & Co. , San Francisco ( 1978 ) .
   Google Scholar
• N. Christofides , Graph Theory An Algorithmic Approach , Academic Press , New York ( 1975 ) .
   Google Scholar
• F. R. K. Chung and F. K. Hwang , “ The largest minimal rectilinear Steiner trees for a set of n points enclosed in a rectangle with given perimeter ,” Networks , 9 , 19 – 36 ( 1979 ).
   Web of Science ®Google Scholar
• E. W. Dijkslra , “ A note on two problems in connection with graphs ,” Numersiche Mathematik , 1 , 269 – 271 ( 1959 ).
   Google Scholar
• S. E. Dreyfus and R. A. Wagner , “ The Steiner problem in graphs ,” Networks , 1 , 195 – 207 ( 1972 ).
   Google Scholar
• L. R. Foulds and R. L. Graham , “ The Steiner problem in phylogeny is NP-complete ,” Advances in Appl. Math. , 3 , 43 – 19 ( 1982 ).
   Google Scholar
• H. Frank and I. T. Frisch , “ Network analysis ,” Large Scale Networks Theory and Design (ed. F. T. Boesche) , IEEE Press , New York , 19 – 27 ( 1976 ).
   Google Scholar
• M. R. Garey , R. L. Graham , and D. S. Johnson , “ Some NP-complete geometric problems ,” Proc. of the 8th Annual Symposium on Theory of Computing , 10 – 22 ( 1976 ).
   Google Scholar
• M. R. Garey , R. L. Graham , and D. S. Johnson , “ The complexity of computing Steiner minimal trees ,” SIAM J. Appl. Math. , 32 , 835 – 859 ( 1977 ).
   Web of Science ®Google Scholar
• M. R. Garey and D. S. Johnson , “ The rectilinear Steiner tree problem is NP-complete ,” SIAM J. Appl. Math. , 32 , 826 – 834 ( 1977 ).
   Web of Science ®Google Scholar
• E. N. Gilbert and H. O. Pollak , “ Steiner minimal trees ”, SIAM J. Appl Math. , 16 , 1 – 29 ( 1968 ).
   Web of Science ®Google Scholar
• R. L. Graham and F. R. K. Chung , Private Communication .
   Google Scholar
• S. L. Hakimi , “ Steiner's problem in graphs and its implications ,” Networks , 1 , 113 – 133 ( 1971 ).
   Google Scholar
• M. Hanan , “ On Steiner's problem with rectlinear distances ,” SIAM J. Appl. Math. , 14 , 255 – 265 ( 1966 ).
   Web of Science ®Google Scholar
• M. Hanan , “ Layout interconnection and placement ,” Networks , 5 , 85 – 88 ( 1975 ).
   Google Scholar
• M. Hanan and J. M. Kurtzburg , “ Placment techniques ,” Design Automation of Digital Systems (ed. M. Breuer) , Prentice-Hall , Englewood Cliffs , New Jersey ( 1972 ) .
   Google Scholar
• F. Harary , Graph Theory , Addison-Wesley , Reading , Mass. ( 1969 ) .
   Google Scholar
• F. K. Hwang , “ On Steiner minimal trees with rectilinear distance ,” SIAM J. Appl. Math. , 30 , 104 – 114 ( 1976 ).
   Web of Science ®Google Scholar
• F. K. Hwang , “ An 0(n log n) Algorithm for suboptimal rectilinear Steiner trees ,” IEEE Trans, on Circuits and Systems , 26 , 75 – 77 ( 1979 ).
   Google Scholar
• R. M. Karp , “ Reducibility among combinatorial problems ,” Complexity of Computer Computations (eds. R. E. Miller and J. W. Thatcher) , Plenum Press , New York , 85 – 104 ( 1972 ).
   Google Scholar
• L. Kou , G. Markowsky , and L. Berman , “ A fast algorithm for Steiner trees ,” Acta Informatica , 15 , 141 – 145 ( 1981 ).
   Web of Science ®Google Scholar
• J. B. Kruskal , “ On the shortest spanning subtree of a graph and the travelling salesman problem ,” Proc. Amer. Math. Soc , 7 , 48 – 50 ( 1956 ).
   Google Scholar
• J. H. Lee , N. K. Bose , and F. K. Hwang , “ Use of Steiner's problem in suboptimal routing in rectilinear metric .” IEEE Trans, on Circuits and Systems , 23 , 470 – 476 ( 1976 ).
   Google Scholar
• A. Levin , “ Algorithm for the shortest connection of a group of graph vertices ,” Soviet Math. Dokladi , 12 , 1477 – 1481 ( 1971 ).
   Google Scholar
• J. MacGregor-Smith , D. T. Lee , and J. S. Liebman , “ An 0(n log n) heuristic algorithm for the rectilinear Steiner minimal tree problem ,” Engineering Optimization , 4 , 179 – 192 ( 1980 ).
   Web of Science ®Google Scholar
• J. MacGregor-Smith and J. S. Liebman , “ Steiner trees, Steiner circuits, and the interference problem in building design ,” Engineering Optimization , 4 , 15 – 36 ( 1979 ).
   Web of Science ®Google Scholar
• Z. A. Melzak , “ On the problem of Steiner ,” Canadian Math. Bulletin , 4 , 143 – 148 ( 1961 ).
   Google Scholar
• R. C. Prim , “ Shortest connection networks and some generalizations ,” Bell Systems Technical Journal , 36 , 1389 – 1401 ( 1957 ).
   Google Scholar
• V. J. Rayward-Smilh , “ The computation of nearly minimal Steiner trees in graphs ,” International Journal of Math. Educ. in Science and Technology , to appear .
   Google Scholar
• M. L. Shore , L. R. Foulds , and P. B. Gibbons , “ Algorithms for the Steiner problem in graphs ,” Networks , 12 , 323 – 333 ( 1982 ).
   Web of Science ®Google Scholar
• H. Takahashi and A. Matsuyama , “ An approximate solution for the Steiner problem in graphs ,” Mathematica Japonica , 6 , 573 – 577 ( 1980 ).
   Google Scholar
• Y. Y. Yang and O. Wing , “ Optimal and suboptimal solution algorithms for the wiring problem ,” Proceedings IEEE International Symposium on Circuit Theory , 154 – 158 ( 1972 ).
   Google Scholar