Call of Papers for Current Volume **************** OnLine Submission of Paper

Volume & Issue no: Volume 3, Issue 7, July 2014


A Simple Algorithm for Steiner Tree Problem in Networks
Author Name:
Sandeep Kumar
ABSTRACT Many problems in combinatorial optimization are known to be NP-hard, and thus it is unlikely that there exists any polynomialtime algorithm to solve them. A number of these problems are of practical interest like Minimum Set Cover, Shortest Superstring, Steiner Tree and Traveling Salesman Problem etc. So people have turned to develop polynomial time approximation algorithms to solve them approximately because efficient optimal solution is not achievable.An α-approximation algorithm runs in polynomial time and it is sure to produce a solution of cost within α times the ptimal cost for any input.Steiner Tree problem is one of the open approximation algorithm problems. In this paper a study of various solutions have been done and we propose a new solution for Steiner Tree Problem in graphs (networks), which give results that are close to optimum on a variety of graphs. Keywords : Approximation Ratio, Optimal Solution, Heuristic, Distance Network
Cite this article:
Sandeep Kumar , " A Simple Algorithm for Steiner Tree Problem in Networks " , International Journal of Application or Innovation in Engineering & Management (IJAIEM) , Volume 3, Issue 7, July 2014 , pp. 232-236 , ISSN 2319 - 4847.
Full Text [PDF]                           Back to Current Issue