Fast Approximation Algorithm for Restricted Euclidean Bottleneck Steiner Tree Problem

Journal of Multimedia

关键词: Wireless Networks;    Performance Ratio;    Approximation Algorithm;    Bottleneck Steiner Tree;   

Others  :  1017231
DOI  :  10.4304/jmm.9.4.522-526

【 摘 要 】

Bottleneck Steiner tree problem asks to find a Steiner tree for n terminals with at most k Steiner points such that the length of the longest edge in the tree is minimized. The problem has applications in the design of wireless communication networks. In this paper we study a restricted version of the bottleneck Steiner tree problem in the Euclidean plane which requires that only degree-2 Steiner points are possibly adjacent in the optimal solution. We first show that the problem is NP-hard and cannot be approximated within unless P=NP, and provide a fast polynomial time deterministic approximation algorithm with performance ratio .

【 授权许可】

   
@ 2006-2014 by ACADEMY PUBLISHER – All rights reserved.