Computing minimum tile sets to self-assemble color patterns

Aleck C. Johnsen; Ming-Yang Kao; Shinnosuke Seki

doi:10.1007/978-3-642-45030-3_65

Computing minimum tile sets to self-assemble color patterns

Aleck C. Johnsen, Ming-Yang Kao, Shinnosuke Seki

Computer Science

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

7 Scopus citations

Abstract

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.

Original language	English (US)
Title of host publication	Algorithms and Computation - 24th International Symposium, ISAAC 2013, Proceedings
Pages	699-710
Number of pages	12
DOIs	https://doi.org/10.1007/978-3-642-45030-3_65
State	Published - Dec 1 2013
Event	24th International Symposium on Algorithms and Computation, ISAAC 2013 - Hong Kong, China Duration: Dec 16 2013 → Dec 18 2013

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	8283 LNCS
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Other

Other	24th International Symposium on Algorithms and Computation, ISAAC 2013
Country/Territory	China
City	Hong Kong
Period	12/16/13 → 12/18/13

ASJC Scopus subject areas

Theoretical Computer Science
Computer Science(all)

Access to Document

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

Cite this

Johnsen, A. C., Kao, M-Y., & Seki, S. (2013). Computing minimum tile sets to self-assemble color patterns. In Algorithms and Computation - 24th International Symposium, ISAAC 2013, Proceedings (pp. 699-710). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 8283 LNCS). https://doi.org/10.1007/978-3-642-45030-3_65

@inproceedings{89392a401cca417b819736d0705e326f,

title = "Computing minimum tile sets to self-assemble color patterns",

abstract = "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.",

author = "Johnsen, {Aleck C.} and Ming-Yang Kao and Shinnosuke Seki",

year = "2013",

month = dec,

day = "1",

doi = "10.1007/978-3-642-45030-3_65",

language = "English (US)",

isbn = "9783642450297",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

pages = "699--710",

booktitle = "Algorithms and Computation - 24th International Symposium, ISAAC 2013, Proceedings",

note = "24th International Symposium on Algorithms and Computation, ISAAC 2013 ; Conference date: 16-12-2013 Through 18-12-2013",

}

Johnsen, AC, Kao, M-Y & Seki, S 2013, Computing minimum tile sets to self-assemble color patterns. in Algorithms and Computation - 24th International Symposium, ISAAC 2013, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 8283 LNCS, pp. 699-710, 24th International Symposium on Algorithms and Computation, ISAAC 2013, Hong Kong, China, 12/16/13. https://doi.org/10.1007/978-3-642-45030-3_65

Computing minimum tile sets to self-assemble color patterns. / Johnsen, Aleck C.; Kao, Ming-Yang; Seki, Shinnosuke.

Algorithms and Computation - 24th International Symposium, ISAAC 2013, Proceedings. 2013. p. 699-710 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 8283 LNCS).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

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 -

Computing minimum tile sets to self-assemble color patterns

Abstract

Publication series

Other

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this