Computing minimum tile sets to self-assemble color patterns

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

Research output: Chapter in Book/Report/Conference proceedingConference contribution

6 Citations (Scopus)

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 languageEnglish (US)
Title of host publicationAlgorithms and Computation - 24th International Symposium, ISAAC 2013, Proceedings
Pages699-710
Number of pages12
DOIs
StatePublished - Dec 1 2013
Event24th International Symposium on Algorithms and Computation, ISAAC 2013 - Hong Kong, China
Duration: Dec 16 2013Dec 18 2013

Publication series

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

Other

Other24th International Symposium on Algorithms and Computation, ISAAC 2013
CountryChina
CityHong Kong
Period12/16/1312/18/13

Fingerprint

Tile
Self-assembly
Self assembly
Color
Synthesis
Computing
NP-hardness
Hardness

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)

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
Johnsen, Aleck C. ; Kao, Ming-Yang ; Seki, Shinnosuke. / Computing minimum tile sets to self-assemble color patterns. Algorithms and Computation - 24th International Symposium, ISAAC 2013, Proceedings. 2013. pp. 699-710 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).
@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 = "12",
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",

}

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 proceedingConference 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

ER -

Johnsen AC, Kao M-Y, Seki S. Computing minimum tile sets to self-assemble color patterns. In 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)). https://doi.org/10.1007/978-3-642-45030-3_65