Abstract
Patterned self-assembly tile set synthesis (pats) aims at minimizing the number of distinct DNA tile types used to self-assemble a given rectangular color pattern. For an integer k, k-pats is the subproblem of pats that restricts input patterns to those with at most k colors. We give an efficient verifier, and based on that, we establish a manually-checkable proof for the NP-hardness of 11-pats; the best previous manually-checkable proof is for 29-pats.
Original language | English |
---|---|
Pages (from-to) | 496–529 |
Number of pages | 34 |
Journal | JOURNAL OF COMBINATORIAL OPTIMIZATION |
Volume | 33 |
Issue number | 2 |
Early online date | 24 Nov 2015 |
DOIs | |
Publication status | Published - 2017 |
MoE publication type | A1 Journal article-refereed |
Keywords
- DNA pattern self-assembly
- Manually-checkable proof
- Tile complexity