TY - GEN

T1 - Computing minimum tile sets to self-assemble color patterns

AU - Johnsen, Aleck C.

AU - Kao, Ming-Yang

AU - Seki, Shinnosuke

PY - 2013/12/1

Y1 - 2013/12/1

N2 - Patterned self-assembly tile set synthesis (PATS) aims at finding a minimum tile set to uniquely self-assemble a given rectangular pattern. For k ≥ 1, k-PATS is a variant of PATS that restricts input patterns to those with at most k colors. We prove the NP-hardness of 29-PATS, where the best known is that of 60-PATS.

AB - Patterned self-assembly tile set synthesis (PATS) aims at finding a minimum tile set to uniquely self-assemble a given rectangular pattern. For k ≥ 1, k-PATS is a variant of PATS that restricts input patterns to those with at most k colors. We prove the NP-hardness of 29-PATS, where the best known is that of 60-PATS.

UR - http://www.scopus.com/inward/record.url?scp=84893408618&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84893408618&partnerID=8YFLogxK

U2 - 10.1007/978-3-642-45030-3_65

DO - 10.1007/978-3-642-45030-3_65

M3 - Conference contribution

AN - SCOPUS:84893408618

SN - 9783642450297

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 699

EP - 710

BT - Algorithms and Computation - 24th International Symposium, ISAAC 2013, Proceedings

T2 - 24th International Symposium on Algorithms and Computation, ISAAC 2013

Y2 - 16 December 2013 through 18 December 2013

ER -