The computation of nearly minimal Steiner trees in graphs

Research output: Contribution to journalArticle

130 Citations (Scopus)

Abstract

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.
Original languageEnglish
Pages (from-to)15-23
Number of pages9
JournalInternational Journal of Mathematical Education in Science and Technology
Volume14
Issue number1
DOIs
Publication statusPublished - Jan 1983

Cite this