YCYongxi Cheng

Yongxi Cheng

*This is an algorithmically generated author record based on publicly available information.

Current Organizations / Institutes

The organizations/institutes from the scholar's latest article


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 publication
  • Guohui Lin

    Department of Computing Science, University of Alberta, Edmonton, Alberta, Canada

    1 shared publication
  • Ker-I Ko

    Department of Computer Science, State University of New York at Stony Brook, Stony Brook, New York

    1 shared publication

Latest Publications

  • On the Parameterized Complexity of Pooling Design

    by Yongxi Cheng, Ding-Zhu Du, Ker-I Ko, Guohui Lin

    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.