【摘 要】
：
The constrained minimum vertex cover problem on bipartite graphs (the Min-CVCB problem) is an important NP-complete problem. This paper presents a polynomial ti
【机 构】
：
School of Information Science and Engineering,Department of Computer Science
论文部分内容阅读
The constrained minimum vertex cover problem on bipartite graphs (the Min-CVCB problem) is an important NP-complete problem. This paper presents a polynomial time approximation algorithm for the problem based on the technique of chain implication. For any given constant ∈ > 0, if an instance of the Min-CVCB problem has a minimum vertex cover of size (ku, kl), our algorithm constructs a vertex cover of size (ku*, kl*), satisfying max{ku*/ku, kl*/kl} ≤ 1 + ∈.
其他文献
A chemoreduction-purge-and-trap gas chromatographic method has been developed for the determination of trace dimethylsulfoxide (DMSO) in seawater.In the analysi
The asymmetric inlet velocity profile has been observed in phantom model using LDA and in health subjects using Magnet Resonance (MR). The effects of asymmetric
The effect of loading rate on the dynamic fracture properties and the failure mechanisms of glass fiber-reinforced composite materials under mode I fracture is
Two novel biscrown ethers with rigid cisltrans ethylene linker were synthesized v/a Wittig reaction in high yield (about 80%).Their pure cis/trans-isomers were
Catalytic oxidation of NO by O2 over La0.8Sr0.2MnO3 was tested in a tubular reactor.The reaction temperature ranged from 373 to 473 K,space time from 0.090 to 0
We report the structural characterization and proposed formation mechanism of honeycomb-like ZnO conglomerationsfabricated by direct precipitation method. X-ray
Six eremophilane sesquiterpenes were obtained from a marine fungus Penicillium sp. BL27-2. Their structures were elucidatedas 3-acetyl-9, 7 (11)-dien-7ot-hydrox
A new ruthenium complex trans-RuCl2(COD)Py2 has been synthesized and charac- terized by elemental analysis, IR, 1H NMR and single-crystal X-ray diffraction. Cry
A series of aza-naphthindolizinedione derivatives, such as indolizinoquinolinedione derivatives, indolizinophthalazinedionederivatives and indolizinoquinoxaline