| Article ID | Journal | Published Year | Pages | File Type |
|---|---|---|---|---|
| 4651557 | Electronic Notes in Discrete Mathematics | 2016 | 11 Pages |
Abstract
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/4n/4, where n is the number of nodes in the given graph.
Keywords
Related Topics
Physical Sciences and Engineering
Mathematics
Discrete Mathematics and Combinatorics
Authors
Divya K, Amal P M, Ajish Kumar K S,