A heuristic for the Steiner problem in graphs |
| |
| Authors: | B N Khoury P M Pardalos |
| |
| Institution: | (1) Center for Applied Optimization, University of Florida, 303 Weil Hall, 32611-6595 Gainesville, FL, USA;(2) ISE Department, University of Florida, 303 Weil Hall, 32611-6595 Gainesville, FL, USA |
| |
| Abstract: | In this paper, we present a heuristic for the Steiner problem in graphs (SPG) 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. |
| |
| Keywords: | Steiner problem heuristics minimum spanning tree testing |
| 本文献已被 SpringerLink 等数据库收录！ |
|
