| Article ID: | iaor19981303 |
| Country: | Netherlands |
| Volume: | 6 |
| Issue: | 1 |
| Start Page Number: | 5 |
| End Page Number: | 14 |
| Publication Date: | Jul 1996 |
| Journal: | Computational Optimization and Applications |
| Authors: | Pardalos Panos M., Khoury B.N. |
| Keywords: | heuristics |
In this paper, we present a heuristic for the Steiner problem in graphs along with some experimental results. The heuristic is based on an approach similar to Prim's algorithm for the minimum spanning tree. However, in this approach, arcs are associated with preference weights which are used to break ties among alternative choices of shortest paths occurring during the course of the algorithm. The preference weights are calculated according to a global view which takes into consideration the effect of all the regular nodes, nodes to be connected, on determining the choice of an arc in the solution tree.