Name
Abstract | ||
|---|---|---|
We investigate the computational complexity of some basic problems regarding non-unique probe selection using separable matrices. In particular, we prove that the minimal d̄-separable matrix problem is DP-complete, and the d̄-separable submatrix with reserved rows problem, which is a generalization of the decision version of the minimum d̄-separable submatrix problem, is Σ2P-complete. |
Year | DOI | Venue |
|---|---|---|
2008 | 10.1016/j.tcs.2007.10.014 | Theoretical Computer Science |
Keywords | DocType | Volume |
Non-unique probe selection,Separable matrices,DP-complete,Σ2P-complete | Journal | 390 |
Issue | ISSN | Citations |
1 | 0304-3975 | 1 |
PageRank | References | Authors |
0.36 | 6 | 3 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Yongxi Cheng | 1 | 125 | 15.23 |
| Ker-I Ko | 2 | 196 | 28.54 |
| Weili Wu | 3 | 2093 | 170.29 |