Steiner problems in graphs: Algorithms and Applications

L. R. Foulds, V. J. Rayward-Smith

Research output: Contribution to journalArticle

15 Citations (Scopus)

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.
Original languageEnglish
Pages (from-to)7-16
Number of pages10
JournalEngineering Optimization
Volume7
Issue number1
DOIs
Publication statusPublished - 1983

Cite this