文摘
In this paper, we introduce a heuristic approximation algorithm for The Steiner Tree problem which is known to be NP Hard. It is based on the concept of degree of each node in the given graph. The Steiner Tree problem is similar to the Minimum Spanning Tree problem with a subset of vertices. The complexity analysis tells us that this method has an approximation ratio of n/4, where n is the number of nodes in the given graph.