A new Steiner tree algorithm based on Sollin's algorithm in graphs

Abstract

The minimum Steiner tree problem, a classical combinatorial optimization problem with a long history, is a NP-complete problem. Due to its wide application, study of heuristic algorithm about Steiner tree problem has important practical and theoretical significance. In this paper, we introduce a new heuristic algorithm based on Sollin's algorithm for solving the Steiner tree problem in graph. We describe our algorithm and its computational results. It is shown that our algorithm has a good performance in achieving a Steiner tree and is comparable with other existing solutions.