No Detail Found!

Improved steiner approximation algorithm based on topology analysis.

Author(s)
Gao Lei Zhang Deyun Gao Lei, School of Electronics and Information Engineering, Xi`an Jiaotong University, Xi`an, Shaanxi, People’s Republic of China
Wang Lei Gao Lei, School of Electronics and Information Engineering, Xi`an Jiaotong University, Xi`an, Shaanxi, People’s Republic of China
Shi Hongfeng Gao Lei, School of Electronics and Information Engineering, Xi`an Jiaotong University, Xi`an, Shaanxi, People’s Republic of China
Abstract
To the case k=3 of the Berman’s approximation algorithm, the improved algorithm is proposed in this study. It constructs a Voronoi region to get the cost of triple subtree on the basis of using Fibonacci heap to count the shortest distance of each pair of points in the corresponding set. Then, to decrease useless triples by the topology analysis of Steiner tree, it simplifies the topology and reduces the time complexity. In the experiment results, the filter factor B is above 0.9 for each example, some even up to 0.999. It shows that many useless triples have been filtered before the beginning of the evaluation phase and the construction phase.
Publication Details
Page(s) 11-15
DOI DOI not available
Published Journal: Information technology Journal, Volume: 4, Issue: 1, Year: 2005

Request the full text from PASTIC

More from Information technology Journal
0

Citations

0

Downloads

60

Views

Copyright ©  PASTIC National Center, Islamabad www.pastic.gov.pk