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)

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.

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
URI:	https://ueaeprints.uea.ac.uk/id/eprint/23891
DOI:	10.1080/0020739830140103

Actions (login required)

View Item