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

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