The Complexity of Computing Steiner Minimal Trees

著者: M. R. Garey, Ronald Graham, David S. Johnson - SIAM Journal on Applied Mathematics 1977 被引用: 575

It is shown that the problem of computing Steiner minimal trees for general planar point sets is inherently at least as difficult as any of the $NP$-complete problems (a well known class of computationally intractable problems). This effectively destroys any hope for finding an efficient algorithm for this problem.