Algorithmic Approach For Restricted Bottleneck Steiner Tree Problem

New applications of traditional Steiner tree problem in VLSI routing, wireless communications and phylogenetic tree reconstruction in biology have been found and studied deeply. These applications generally need to do some modification to the traditional Steiner tree problem. Therefore, the study of variations of traditional Steiner tree problem become a hot issue. The variations of the traditional Steiner tree problem contain the bottleneck Steiner tree problem and the Steiner tree problem with minimum number of Steiner points and bounded edge-length.The main content of this paper is the bottleneck Steiner tree problem, which asks to find a Steiner tree for n terminals with at most k Steiner nodes such that the length of the longest edge in the tree is minimized.In the study of bottleneck Steiner tree problem, L. Wang and D.-Z Du showed that unless P=NP, the problem cannot be approximated within ratio 2 and (?) in polynomial time for the rectilinear and Euclidean plane, respectively. Then they proposed a polynomial time approximation algorithm with performance ratio 2 for both the two planes by using the triangle inequality property of terminals and 2-restricted Steiner subtree.Z. Li and D.-Z Du deeply studied the geometric relationship between terminals and notion of 3-restricted Steiner subtree, they designed approximation algorithms with performance ratio 1.866+? and (?)+? for the problem in the Euclidean plane, respectively, here ? is an arbitrary positive number. However, the gap between the lower bound (?) and approximation ratio (?) was still big.Then Z. Li etc. considered a restricted version of the problem which requires that any two Steiner points are not adjacent in the optimal solution. According to the existence of 2-restricted Steiner subtree and 3-restricted Steiner subtree, they proved the existence of performance ratio (?) and (?), and presented corresponding approximation algorithms.This dissertation studies two restricted versions of the bottleneck Steiner tree problem in the Euclidean plane:(1) only degree=2 Steiner points are allowed to be adjacent in the optimal solution, (2) only degree>3 Steiner points are not allowed to be adjacent in the optimal solution. The two restricted versions are more general than that considered by Z. Li etc., and the latter one is more general than the former and is closer to the original bottleneck Steiner tree problem.By a reduction from the restricted version of the planar vertex cover problem, we prove that the two new restricted problem is NP-hard. Then for the first restricted version, we show the existence of performance ratio (?) and (?), and present a polynomial time deterministic ratio- (?) approximation algorithm and a polynomial time randomized ratio-(?)+? approximation algorithm. By introducing the binary maximum heap and binary search technology, we improve the time complexity of the two approximation algorithms, respectively; For the second restricted problem in the Euclidean plane, we also prove the existence of performance ratio (?) and (?), show that the deterministic ratio-(?) approximation algorithm for the first restricted version can be applied to the second directly, and finally present a polynomial time randomized ratio-(?)+? approximation algorithm, which almost close the problem.