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.
|Number of pages||9|
|Journal||International Journal of Mathematical Education in Science and Technology|
|Publication status||Published - Jan 1983|