Competitive Decision Algorithm for the Steiner Minimal Tree Problem in Graphs
Ning Ai-bing · Journal of the University of Shanghai for Science and Technology · 2012
The Steiner minimal tree problem in graphs(GSTP) is a well-known NP-hard problem.Its applications can be found in many areas,such as telecommunication network design,VLSI design,etc.A competitive decision algorithm was developed to solve the GSTP.The mathematical properties of GSTP were analysed,which can be used to scale down the size of original problem and accelerate the algorithm.To assess the efficiency of the proposed competitive decision algorithm,it was applied to a set of benchmark problems in the OR-Library.In terms of computation times,our algorithm clearly outperforms other heuristics for the Steiner problem in graphs,while obtaining better or comparable solutions.