Volume & Issue no: Volume 3, Issue 7, July 2014
_____________________________________________________________________________
Title: |
A Simple Algorithm for Steiner Tree Problem in Networks
|
Author Name: |
Sandeep Kumar |
Abstract: |
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  |
|
