An Inspiration for Recent Innovation & Research….
ISSN 2319 – 4847
www.ijaiem.org
Call for Paper, Published Articles, Indexing Infromation
International Journal of Application or Innovation in Engineering & Management
An Inspiration for Recent Innovation & Research….
ISSN 2319 – 4847
www.ijaiem.org
Call for Paper, Published Articles, Indexing Infromation
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.
|