The computation of nearly minimal Steiner trees in graphs

The computation of a minimal Steiner tree for a general weighted graph is known to be NP‐hard. Except for very simple cases, it is thus computationally impracticable to use an algorithm which produces an exact solution. This paper describes a heuristic algorithm which runs in polynomial time and produces a near minimal solution. Experimental results show that the algorithm performs satisfactorily in the rectilinear case. The paper provides an interesting case study of NP‐hard problems and of the important technique of heuristic evaluation.