Gao Lei
School of Electronics and Information Engineering,
Xian Jiaotong University, Xian, Shaanxi, Peoples Republic of China
Zhang Deyun
School of Electronics and Information Engineering,
Xian Jiaotong University, Xian, Shaanxi, Peoples Republic of China
Wang Lei
School of Electronics and Information Engineering,
Xian Jiaotong University, Xian, Shaanxi, Peoples Republic of China
Shi Hongfeng
School of Electronics and Information Engineering,
Xian Jiaotong University, Xian, Shaanxi, Peoples 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 Steinertree, it simplifies the topology and reduces the time complexity. In the experiment results, the filter factor β 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.
PDF References Citation
How to cite this article
Gao Lei, Zhang Deyun, Wang Lei and Shi Hongfeng, 2005. Improved Steiner Approximation Algorithm Based on Topology Analysis. Information Technology Journal, 4: 11-15.
DOI: 10.3923/itj.2005.11.15
URL: https://scialert.net/abstract/?doi=itj.2005.11.15
DOI: 10.3923/itj.2005.11.15
URL: https://scialert.net/abstract/?doi=itj.2005.11.15
REFERENCES
- Ganley, J.L., 1999. Computing optimal rectilinear Steiner trees: A survey and experimental evaluation. Discrete. Applied Maths., 90: 161-171.
CrossRefDirect Link - Fredman, M.L. and R.E. Tarjan, 1987. Fibonacci heaps and their uses in improved network optimization algorithms. J. Assoc. Computer, 34: 596-615.
CrossRefDirect Link