Networks · 1995 · 15 citations · 29 references
ComputingComputer ScienceMathematicsAlgorithmsComputational GeometryOptimizationCombinatorial OptimizationComputational ComplexityDelaunay TriangulationsGraph AlgorithmsGraph TheoryHeuristic OptimizationDelaunay Triangulation AlgorithmsHeuristic AlgorithmsNp-hardnessPolynomial Time ComplexityPolynomial-time AlgorithmsSteiner Tree ProblemTree AlgorithmsTriangulation Algorithms
Abstract Even though the problem of computing Steiner minimal trees (SMTs) in the plane is well known to be NP ‐hard, There exist heuristic algorithms which run in polynomial time. Recent research results have shown that the problem in three dimensions is demonstrably more difficult. This paper approaches the development of a heuristic for the problem utilizing the Delaunay triangulation in 3‐space to compute suboptimal SMTs. Computational results are also provided.
29
E. N. Gilbert, H. O. Pollak · SIAM Journal on Applied Mathematics · 1968 · 938 citations
F. K. Hwang, Dana Richards · Networks · 1992 · 664 citations
Steiner problem in networks: A survey
Paweł Winter · Networks · 1987 · 594 citations