A degree based approach to find Steiner Trees
详细信息    查看全文
文摘
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.

© 2004-2018 中国地质图书馆版权所有 京ICP备05064691号 京公网安备11010802017129号

地址:北京市海淀区学院路29号 邮编:100083

电话:办公室:(+86 10)66554848;文献借阅、咨询服务、科技查新:66554700