STEINER PROBLEMS IN GRAPHS: ALGORITHMS AND APPLICATIONS |
| |
| Authors: | L R FOULDS V J RAYWARD-SMITH |
| |
| Affiliation: | 1. University of Florida , Gainesville, U.S.A;2. University of East Anglia , Norwich, U.K |
| |
| 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. |
| |
| Keywords: | |
|
|
