An improved algorithm for Steiner trees
Peiliang Qiu · Journal of China Institute of Communications · 2002
Minimum Steiner tree problem is NP complete problem. There are theoretic and realistic significance to research heuristic for Steiner problem. In this paper, a new algorithm KBMPH in which some short paths which pass through some key nodes are more likely to be chosen first is presented. It is based on MPH algorithm. The simulation results on random networks show that in almost all cases the cost of KBMPH trees is lower than that of MPH algorithm. The complexity of KBMPH is )(3nO.