【摘 要】
：
A special case of the bottleneck Steiner tree problem in the Euclidean plane was considered in this paper. The problem has applications in the design of wireles
【机 构】
：
School of Computer Science and Technology
【基金项目】
：
国家自然科学基金;山东省优秀中青年科学家科研奖励基金
论文部分内容阅读
A special case of the bottleneck Steiner tree problem in the Euclidean plane was considered in this paper. The problem has applications in the design of wireless communication networks, multifacility location, VLSI routing and network routing. For the special case which requires that there should be no edge connecting any two Steiner points in the optimal solution, a 3-restricted Steiner tree can be found indicating the existence of the performance ratio √2. In this paper, the special case of the problem is proved to be NP-hard and cannot be approximated within ratio √2. First a simple polynomial time approximation algorithm with performance ratio √3 is presented. Then based on this algorithm and the existence of the 3-restricted Steiner tree, a polynomial time approximation algorithm with performance ratio-√2 + ε is proposed, for any ε＞0.
其他文献
Using core-scattered closed-orbit theory and region-splitting iterative method, we calculated the scaled recurrence spectra of helium atom in parallel electric
Mining frequent patterns from datasets is one of the key success of data mining research. Currently, most of the studies focus on the data sets in which the ele
The knapsack problem is well known to be NP-complete. Due to its importance in cryptosystem and in number theory, in the past two decades, much effort has been
For a composite system of gravitationally coupled stellar and gaseous discs, we have carried out a linear stability analysis for axisymmetric coplanar perturbat
X-ray photoelectron spectroscopy(XPS) and extended X-ray absorption fine structure(EXAFS) were used to characterize the structure of the mixture of molybdenum o
合成了标题配合物[Ni(en)3]2+H2dsh2- (H4dsh = 1,2-二水杨酰基肼)。晶体属正交晶系, 分子式为C20H34N8NiO4, 空间群为P212121。a = 10.5094(4), b = 12.5003(8), c = 17.487
three kinds of N-(diisopropyloxyphosphoryl) amino acids containing hydroxyl group were prepared in high yield by using diisopropyl phosphite as the phosphorylat
From the points of both molten cast iron structure and the appearing ratio of electrons in outer-layer of different atoms, analysis on enhancement mechanism of
We investigate tricritical behavior of the O(n) model in two dimensions by means of transfer-matrix and finite-size scaling methods. For this purpose we conside
Organo-soluble alicyclic polyimides (ALPIs) were synthesized from an alicyclic dianhydride, 1,8-dimethylbicyclo[2.2.2] oct-7-ene-2,3,5,6-tetracarboxylic dianhyd