Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
395232 | Information Sciences | 2010 | 10 Pages |
Abstract
Assume that there exists a collection C of subsets of a finite set S, and a positive integer K ⩽ â£Sâ£, and we need to know whether there is a subset Sâ²Â â S with â£Sâ²â£Â ⩽ K such that Sâ² contains at least one element of each subset in C. In other words, Sâ² is the subset that intersects every subset in C and is called the hitting-set. In this paper, a DNA-based algorithm is proposed to solve the small hitting-set problem. A small hitting-set is a hitting-set with the smallest K value, i.e., the hitting-set with the smallest number of elements. Furthermore, another algorithm is introduced to find the number of ones from 2n combinations and minimum numbers of ones represents the small hitting-set since K is expected to be as small as possible. The complexity of the proposed DNA-based algorithm is discussed, in terms of time complexity, volume complexity, numbers of test tube used and the longest library strand in solution space. Finally, the simulated experiment is applied to verify the correctness of our proposed DNA-based algorithm, in order to solve the well-known hitting-set problem.
Keywords
Related Topics
Physical Sciences and Engineering
Computer Science
Artificial Intelligence
Authors
Nung-Yue Shi, Chih-Ping Chu,