The computation of nearly minimal Steiner trees in graphs

Rayward-Smith, Victor J. (1983) The computation of nearly minimal Steiner trees in graphs. International Journal of Mathematical Education in Science and Technology, 14 (1). pp. 15-23. ISSN 0020-739X

Full text not available from this repository. (Request a copy)


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.

Item Type: Article
Faculty \ School: Faculty of Science > School of Computing Sciences
Depositing User: Vishal Gautam
Date Deposited: 08 Mar 2011 12:45
Last Modified: 15 Dec 2022 02:13
DOI: 10.1080/0020739830140103

Actions (login required)

View Item View Item