An improved heuristic approach for the Steiner tree problem in graphs

The Steiner problem in graphs is known to be an NP-Complete problem. Numerous heuristic approaches for solving this problem have been proposed. Most of them aim at finding the shortest path between a group of nodes and the regular node that is closest to that group. In contrast, our heuristic algorithms attempts to find the minimal distance amongst a group of nodes and the two regular nodes that are closest to the group. We compare our algorithm with a well-known heuristic algorithm and find that our solution is better. In addition, our experiments show that the accuracy of our algorithm is very close to optimal. ^ We also propose a parallel and a distributed version of our algorithms, in order to achieve speedup. In the end, we provide an interesting application for our proposed algorithms.