Yongxi Cheng
Current Organizations / Institutes
The organizations/institutes from the scholar's latest article
Research Subjects
Yongxi Cheng has a total of 3 co-authors. Here are the top co-authors by number of shared publications:
Ding-Zhu Du
Department of Computer Science, University of Texas at Dallas, Richardson, Texas
1 shared publicationGuohui Lin
Department of Computing Science, University of Alberta, Edmonton, Alberta, Canada
1 shared publicationKer-I Ko
Department of Computer Science, State University of New York at Stony Brook, Stony Brook, New York
1 shared publication
Latest Publications
- 1 November 2009
- Published by SAGE Publications in Journal of Computational Biology
- Vol. 16 (11) , 1529-1537
On the Parameterized Complexity of Pooling Design
Pooling design is a very helpful tool for reducing the number of tests in DNA library screening, which is a key process to obtain high-quality DNA libraries for studying gene functions. Three basic problems in pooling design are, given an m × n binary matrix and a positive integer d, to decide whether the matrix is d-separable (d̄-separable, or d-disjunct). The three problems are all known to be coNP-complete. Since in most applications, d is a small integer compared to n, it is interesting to investigate whether there are efficient algorithms solving the above problems when the value of d is small. In this article, we give a negative answer to the above question by studying the parameterized complexity of these three problems, with d as the parameter. We show that the parameterized versions of all the three problems are co-W[2]-complete. An immediate implication of our results is that, given an m × n binary matrix and a positive integer d, a deterministic algorithm with running time f(d) × (mn)O(1) (where f is an arbitrary computable function) to decide whether the matrix is d-separable (d̄-separable, or d-disjunct) should not be expected.
- 1 November 2009
- Published by SAGE Publications in Journal of Computational Biology
- Vol. 16 (11) , 1529-1537
On the Parameterized Complexity of Pooling Design
Pooling design is a very helpful tool for reducing the number of tests in DNA library screening, which is a key process to obtain high-quality DNA libraries for studying gene functions. Three basic problems in pooling design are, given an m × n binary matrix and a positive integer d, to decide whether the matrix is d-separable (d̄-separable, or d-disjunct). The three problems are all known to be coNP-complete. Since in most applications, d is a small integer compared to n, it is interesting to investigate whether there are efficient algorithms solving the above problems when the value of d is small. In this article, we give a negative answer to the above question by studying the parameterized complexity of these three problems, with d as the parameter. We show that the parameterized versions of all the three problems are co-W[2]-complete. An immediate implication of our results is that, given an m × n binary matrix and a positive integer d, a deterministic algorithm with running time f(d) × (mn)O(1) (where f is an arbitrary computable function) to decide whether the matrix is d-separable (d̄-separable, or d-disjunct) should not be expected.