Steiner problems in graphs: Algorithms and Applications

Foulds, L. R. and Rayward-Smith, V. J. (1983) Steiner problems in graphs: Algorithms and Applications. Engineering Optimization, 7 (1). pp. 7-16. ISSN 0305-215X

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

Abstract

Consider an undirected graph G = (V, E) with positive edge weights and a nonempty set S ? V, where Vand E are the sets of vertices and edges of G respectively. The Steiner problem in graphs is that of finding a subgraph of G which spans S and is of minimum total edge weight. In this paper we survey solution procedures for this problem. As the associated decision problem is NP-Complete we place special emphasis on heuristic methods of solution. We also examine special cases, related problems, and applications. The paper concludes with ideas for the development of new, efficient heuristics.

Item Type:	Article
Faculty \ School:	Faculty of Science > School of Computing Sciences
Depositing User:	Vishal Gautam
Date Deposited:	10 Mar 2011 09:13
Last Modified:	15 Dec 2022 02:13
URI:	https://ueaeprints.uea.ac.uk/id/eprint/23728
DOI:	10.1080/03052158308960625

Actions (login required)

View Item