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 \(\mathcal{NP}\)-hardness of 29-PATS, where the best known is that of 60-PATS.
This work is supported in part by NSF Grants CCF-1049899 and CCF-1217770 to A. J. and M-Y. K.; and HIIT Pump Priming Grants No. 902184/T30606 and Academy of Finland, Postdoctoral Researcher Grants 13266670/T30606 to S. S.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Adleman, L.: Towards a mathematical theory of self-assembly. Tech. Rep. 00-722, USC (2000)
Barish, R., Schulman, R., Rothemund, P.W.K., Winfree, E.: An Information-bearing seed for nucleating algorithmic self-assembly. Proc. Natl. Acad. Sci. 106, 6054–6059 (2009)
Brun, Y.: Solving \(\mathcal{NP}\)-Complete Problems in the Tile Assembly Model. Theo. Comp. Sci. 395, 31–46 (2008)
Ma, X., Lombardi, F.: Synthesis of tile sets for DNA self-assembly. IEEE T. Comput. Aid. D. 27(5), 963–967 (2008)
Ma, X., Lombardi, F.: On the computation complexity of tile set synthesis for DNA self-assembly. IEEE T. Circuits-II 56(1), 31–35 (2009)
Rothemund, P.W.K., Papadakis, N., Winfree, E.: Algorithmic Self-Assembly of DNA Sierpinski Triangles. PLos Biology 2, 2041–2053 (2004)
Rothemund, P.W.K., Winfree, E.: The program-size complexity of self-assembled squares. In: Proc. of STOC 2000, pp. 459–468 (2000)
Seki, S.: Combinatorial Optimization in Pattern Assembly. In: Mauri, G., Dennunzio, A., Manzoni, L., Porreca, A.E. (eds.) UCNC 2013. LNCS, vol. 7956, pp. 220–231. Springer, Heidelberg (2013)
Winfree, E.: On the Computational Power of DNA Annealing and Ligation. DNA Based Computers, 199–221 (1996)
Winfree, E.: Algorithmic Self-Assembly of DNA. Ph.D. thesis, California Institute of Technology (June 1998)
Winfree, E., Liu, F., Wenzler, L.A., Seeman, N.C.: Design and self-assembly of two-dimensional DNA crystals. Nature 394, 539–544 (1998)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2013 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Johnsen, A.C., Kao, MY., Seki, S. (2013). Computing Minimum Tile Sets to Self-Assemble Color Patterns. In: Cai, L., Cheng, SW., Lam, TW. (eds) Algorithms and Computation. ISAAC 2013. Lecture Notes in Computer Science, vol 8283. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-45030-3_65
Download citation
DOI: https://doi.org/10.1007/978-3-642-45030-3_65
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-45029-7
Online ISBN: 978-3-642-45030-3
eBook Packages: Computer ScienceComputer Science (R0)