【摘 要】
:
Steiner connected dominating set (SCDS) is a generalization of the famous connected dominating set problem,where only a specified set of required vertices has t
【机 构】
:
National High Performance Computing Center at Hefei
【基金项目】
:
\"Research on Routing and Wave length assignment in WDM All-optical Networks\";国家自然科学基金
论文部分内容阅读
Steiner connected dominating set (SCDS) is a generalization of the famous connected dominating set problem,where only a specified set of required vertices has to be dominated by a connected dominating set, and known to be NPhard. This paper firstly modifies the SCDS algorithm of Guha and Khuller and achieves a worst case approximation ratio of (2 + 1/(m - 1))H(min(△, k)) + O(1), which outperforms the previous best result (c + 1)H(min(△, k)) + O(1) in the case of m ≥ 1 + 1/(c - 1), where c is the best approximation ratio for Steiner tree, △ is the maximum degree of the graph, k is the cardinality of the set of required vertices, m is an optional integer satisfying 0 ≤ m ≤ min(△, k) and H is the harmonic function. This paper also proposes another approximation algorithm which is based on a greedy approach. The second algorithm can establish a worst case approximation ratio of 2ln(min(△, k)) + O(1), which can also be improved to 2 ln k if the optimal solution is greater than c.e2c+1/2(c+1) .
其他文献
The elctrochemical behavior of dissolved Fe2O3 in 82.5CaCl2-17.5KF(mole percent,%)was studied using cyclic voltammetry,chronoamperometry,and galvanostatic elect
Azoxy dyes and their copper complexes with maximum dichroism in the spectrum range from 550 nm to 700 nm were synthesized and used to prepare polyvinyl alcohol
Amino acids are the building blocks to build peptides and proteins. Recent development in peptide synthesis has however enabled us to mimic this natural process
The convergence rate of the power inversion (PI) algorithm is quite sensitive to the power of the interference with the used fixed parameters in the PI algorith
In order to investigate the inhibitory effect of matrine on the expression of prostate specific antigen (PSA) and. Androgen receptor (AR) in prostate cancer cel
Co-55 (t1/2=17.53 h) was produced by 150 μA irradiation of a natural nickel target using 15 MeV protons. It was separated from the irradiated target material b
The linear variable separation approach is successfully extended to (1+ 1)-dimensional Korteweg-de Vries (KdV) type models related to Schrodinger system. Some s
A new monolithic Ni/CeO2-ZrO2/γ-Al2O3 catalyst for combined partial oxidation and CO2 reforming of methane was prepared. The result shows that the addition of
Phenylalkanes with carbon numbers between 16 and 19,characterized by the main carbon-18,have been identified in the mod-em sediments collected from gas hydrate
The spallation of the concrete slabs or walls resulting from contact detonation constitutes risk to the personnel and equipment inside the structures because of