Nearly Optimal Solution for Restricted Euclidean Bottleneck Steiner Tree Problem

Journal of Networks

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

Others  :  1017551
DOI  :  10.4304/jnw.9.4.1000-1004

【 摘 要 】

A variation of the traditional Steiner tree problem, the bottleneck Steiner tree problem is considered in this paper, which 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 WDM optical networks, design of wireless communication networks and reconstruction of phylogenetic tree in biology. 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. The problem is known to be MAX-SNP hard and cannot be approximated within unless P=NP, we propose a nearly optimal randomized polynomial time approximation algorithm with performance ratio+e, where e is a positive number.

【 授权许可】

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