{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2023,1,31]],"date-time":"2023-01-31T19:54:42Z","timestamp":1675194882627},"reference-count":39,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2007,10,2]],"date-time":"2007-10-02T00:00:00Z","timestamp":1191283200000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Nat Comput"],"published-print":{"date-parts":[[2008,6]]},"DOI":"10.1007\/s11047-007-9048-6","type":"journal-article","created":{"date-parts":[[2007,10,1]],"date-time":"2007-10-01T13:26:45Z","timestamp":1191245205000},"page":"183-201","source":"Crossref","is-referenced-by-count":3,"title":["On the complexity of graph self-assembly in accretive systems"],"prefix":"10.1007","volume":"7","author":[{"given":"Stanislav","family":"Angelov","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Sanjeev","family":"Khanna","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Mirk\u00f3","family":"Visontai","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2007,10,2]]},"reference":[{"key":"9048_CR1","doi-asserted-by":"crossref","unstructured":"Adleman LM, Cheng Q, Goel A, Huang MDA (2001) Running time and program size for self-assembled squares. In: Proceedings of the 33th Annual ACM Symposium on Theory of Computing, 740\u2013748","DOI":"10.1145\/380752.380881"},{"key":"9048_CR2","doi-asserted-by":"crossref","unstructured":"Adleman LM, Cheng Q, Goel A, Huang MDA, Kempe D, de Espan\u00e9es PM, Rothemund PWK (2002) Combinatorial optimization problems in self-assembly. In: Proceedings of the 34th Annual ACM Symposium on Theory of Computing, 23\u201332","DOI":"10.1145\/509907.509913"},{"key":"9048_CR3","unstructured":"Aggarwal G, Goldwasser M, Kao MY, Schweller RT (2004) Complexities for generalized models of self-assembly. In: Proceedings of the 15th annual ACM-SIAM Symposium on Discrete Algorithms, 880\u2013889"},{"issue":"12","key":"9048_CR4","doi-asserted-by":"crossref","first-page":"2586","DOI":"10.1021\/nl052038l","volume":"5","author":"RD Barish","year":"2005","unstructured":"Barish RD, Rothemund PWK, Winfree E (2005) Two computational primitives for algorithmic self-assembly: copying and counting. Nano Lett 5(12):2586\u20132592","journal-title":"Nano Lett"},{"issue":"2","key":"9048_CR5","doi-asserted-by":"crossref","first-page":"259","DOI":"10.7151\/dmgt.1053","volume":"17","author":"H Broersma","year":"1997","unstructured":"Broersma H, Li X (1997) Spanning trees with many or few colors in edge-colored graphs. Discussiones Mathematicae Graph Theory 17(2):259\u2013269","journal-title":"Discussiones Mathematicae Graph Theory"},{"issue":"43","key":"9048_CR6","doi-asserted-by":"crossref","first-page":"13924","DOI":"10.1021\/ja0458120","volume":"126","author":"N Chelyapov","year":"2004","unstructured":"Chelyapov N, Brun Y, Gopalkrishnan M, Reishus D, Shaw B, Adleman LM (2004) DNA triangles and self-assembled hexagonal tilings. J Am Chem Soc 126(43):13924\u201313925","journal-title":"J Am Chem Soc"},{"key":"9048_CR7","unstructured":"Chen HL, Cheng Q, Goel A, Huang MDA, de Espan\u00e9s PM (2004) Invadable selfassembly: combining robustness with efficiency. In: Proceedings of the 15th annual ACM-SIAM Symposium on Discrete Algorithms, 890\u2013899"},{"key":"9048_CR8","unstructured":"Chen HL, Goel A (2004) Error free self-assembly using error prone tiles. In: Proceedings of the 10th International Workshop on DNA Computing, 62\u201375"},{"key":"9048_CR9","unstructured":"Cook M, Rothemund PWK, Winfree E (2003) Self-assembled circuit patterns. In: Proceedings of the 9th International Workshop on DNA Based Computers, 91\u2013107"},{"key":"9048_CR10","unstructured":"Fujibayashi K, Murata S (2004) A method of error suppression for self-assembling DNA tiles. In: Proceedings of the 10th International Workshop on DNA Computing, 113\u2013127"},{"issue":"35","key":"9048_CR11","doi-asserted-by":"crossref","first-page":"12202","DOI":"10.1021\/ja0541938","volume":"127","author":"Y He","year":"2005","unstructured":"He Y, Chen Y, Liu H, Ribbe AE, Mao C (2005) Self-assembly of hexagonal DNA two-dimensional (2D) arrays. J Am Chem Soc 127(35):12202\u201312203","journal-title":"J Am Chem Soc"},{"key":"9048_CR12","doi-asserted-by":"crossref","first-page":"143","DOI":"10.1016\/S0303-2647(99)00041-6","volume":"52","author":"N Jonoska","year":"1999","unstructured":"Jonoska N, Karl SA, Saito M (1999) Three dimensional DNA structures in computing. BioSystems 52:143\u2013153","journal-title":"BioSystems"},{"key":"9048_CR13","doi-asserted-by":"crossref","unstructured":"Jonoska N, McColm GL (2005) A computational model for self-assembling flexible tiles. In: Proceedings of the 4th International Conference on Unconventional Computation, 142\u2013156","DOI":"10.1007\/11560319_14"},{"issue":"2","key":"9048_CR14","doi-asserted-by":"crossref","first-page":"123","DOI":"10.1023\/A:1023980828489","volume":"4","author":"N Jonoska","year":"2003","unstructured":"Jonoska N, Sa-Ardyen P, Seeman NC (2003) Computation by self-assembly of DNA graphs. Genetic Program Evolvable Machines 4(2):123\u2013137","journal-title":"Genetic Program Evolvable Machines"},{"key":"9048_CR15","doi-asserted-by":"crossref","unstructured":"Kao MY, Schweller R (2006) Reducing tile complexity for self-assembly through temperature programming. In: Proceedings of the 17th annual ACM-SIAM Symposium on Discrete Algorithms, 571\u2013580","DOI":"10.1145\/1109557.1109620"},{"key":"9048_CR16","unstructured":"Klavins E (2004) Directed self-assembly using graph grammars. In: Proceedings of the 3rd Conference on Foundations of Nanoscience: self-assembled architectures and devices"},{"key":"9048_CR17","doi-asserted-by":"crossref","unstructured":"Klavins E, Ghrist R, Lipsky D (2004) Graph grammars for self-assembling robotic systems. In: Proceedings of the IEEE International Conference on Robotics and Automation, vol. 5:5293\u20135300","DOI":"10.1109\/ROBOT.2004.1302558"},{"issue":"9","key":"9048_CR18","doi-asserted-by":"crossref","first-page":"1848","DOI":"10.1021\/ja993393e","volume":"122","author":"TH LaBean","year":"2000","unstructured":"LaBean TH, Yan H, Kopatsch J, Liu F, Winfree E, Reif JH, Seeman NC (2000) Construction, analysis, ligation, and self-assembly of DNA triple crossover complexes. J Am Chem Soc 122(9):1848\u20131860","journal-title":"J Am Chem Soc"},{"key":"9048_CR19","unstructured":"Lagoudakis MG, LaBean TH (1999) 2D DNA self-assembly for satisfiability. In: Proceedings of the 5th DIMACS International Meeting on DNA Based Computers, 139\u2013152"},{"issue":"2","key":"9048_CR20","doi-asserted-by":"crossref","first-page":"329","DOI":"10.1137\/0211025","volume":"11","author":"D Lichtenstein","year":"1982","unstructured":"Lichtenstein D (1982) Planar formulae and their uses. SIAM J Comp 11(2):329\u2013343","journal-title":"SIAM J Comp"},{"issue":"20","key":"9048_CR21","doi-asserted-by":"crossref","first-page":"3057","DOI":"10.1002\/anie.200463027","volume":"44","author":"J Malo","year":"2005","unstructured":"Malo J, Mitchell JC, Vnien-Bryan C, Harris JR, Wille H, Sherratt DJ, Turberfield AJ (2005) Engineering a 2D protein-DNA crystal. Angewandte Chemie Int Edn 44(20):3057\u20133061","journal-title":"Angewandte Chemie Int Edn"},{"issue":"3","key":"9048_CR22","doi-asserted-by":"crossref","first-page":"2571","DOI":"10.1103\/PhysRevE.59.2571","volume":"59","author":"AA Middleton","year":"1999","unstructured":"Middleton AA (1999) Computational complexity of determining the barriers to interface motion in random systems. Phys Rev E 59(3):2571\u20132577","journal-title":"Phys Rev E"},{"issue":"4","key":"9048_CR23","doi-asserted-by":"crossref","first-page":"199","DOI":"10.1016\/0020-0190(79)90023-1","volume":"8","author":"J Plesn\u03afk","year":"1979","unstructured":"Plesn\u00edk J (1979) The NP-completeness of the Hamiltonian cycle problem in planar digraphs with degree bound two. Inf Process Lett 8(4):199\u2013201","journal-title":"Inf Process Lett"},{"key":"9048_CR24","unstructured":"Reif JH, Sahu S, Yin P (2004) Compact error-resilient computational DNA tiling assemblies. In: Proceedings of the 10th International Workshop on DNA Computing 293\u2013307"},{"key":"9048_CR25","unstructured":"Reif JH, Sahu S, Yin P (2005) Complexity of graph self-assembly in accretive systems and self-destructible systems. In: Proceedings of the 11th International Meeting on DNA Computing, 101\u2013112"},{"issue":"3","key":"9048_CR26","doi-asserted-by":"crossref","first-page":"984","DOI":"10.1073\/pnas.97.3.984","volume":"97","author":"PWK Rothemund","year":"2000","unstructured":"Rothemund PWK (2000) Using lateral capillary forces to compute by self-assembly. Proc Nat Acad Sci USA 97(3):984\u2013989","journal-title":"Proc Natl Acad Sci USA"},{"issue":"12","key":"9048_CR27","first-page":"2041","volume":"2","author":"PWK Rothemund","year":"2004","unstructured":"Rothemund PWK, Papadakis N, Winfree E (2004) Algorithmic self-assembly of DNA Sierpinski triangles. PLoS Biol 2(12):2041\u20132053","journal-title":"PLoS Biol"},{"key":"9048_CR28","doi-asserted-by":"crossref","unstructured":"Rothemund PWK, Winfree E (2000) The program-size complexity of self-assembled squares (extended abstract). In: Proceedings of the 32th Annual ACM Symposium on Theory of Computing, 459\u2013468","DOI":"10.1145\/335305.335358"},{"issue":"21","key":"9048_CR29","doi-asserted-by":"crossref","first-page":"6648","DOI":"10.1021\/ja049953d","volume":"126","author":"P Sa-Ardyen","year":"2004","unstructured":"Sa-Ardyen P, Jonoska N, Seeman NC (2004) Self-assembly of irregular graphs whose edges are DNA helix axes. J Am Chem Soc 126(21):6648\u20136657, ISSN 0002-7863","journal-title":"J Am Chem Soc"},{"issue":"4","key":"9048_CR30","doi-asserted-by":"crossref","first-page":"427","DOI":"10.1023\/B:NACO.0000006771.95566.34","volume":"2","author":"P Sa-Ardyen","year":"2003","unstructured":"Sa-Ardyen P, Jonoska N, Seeman NC (2003) Self-assembling DNA graphs. Nat Comp 2(4):427\u2013438","journal-title":"Nat Comp"},{"key":"9048_CR31","unstructured":"Sahu S, Yin P, Reif JH (2005) A self-assembly model of DNA tiles with time dependent glue strength. In: Proceedings of the 11th International Meeting on DNA Computing, 113\u2013124"},{"key":"9048_CR32","unstructured":"Schulman R, Lee S, Papadakis N, Winfree E (2003) One dimensional boundaries for DNA tile self-assembly. In: Proceedings of the 9th International Workshop on DNA Based Computers, 108\u2013126"},{"key":"9048_CR33","unstructured":"Schulman R, Winfree E (2004) Programmable control of nucleation for algorithmic self-assembly. In: Proceedings of the 10th International Workshop on DNA Computing, 319\u2013328"},{"key":"9048_CR34","unstructured":"Soloveichik D, Winfree E (2004) Complexity of self-assembled shapes. In: Proceedings of the 10th International Workshop on DNA Computing, 344\u2013354"},{"key":"9048_CR35","unstructured":"Soloveichik D, Winfree E (2005) Complexity of compact proofreading for selfassembled patterns. In: Proceedings of the 11th International Meeting on DNA Computing, 125\u2013135"},{"key":"9048_CR36","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1002\/j.1538-7305.1961.tb03975.x","volume":"40","author":"H Wang","year":"1961","unstructured":"Wang H (1961) Proving theorems by pattern recognition II. Bell Syst Tech J 40:1\u201341","journal-title":"Bell Syst Tech J"},{"key":"9048_CR37","unstructured":"Winfree E, Bekbolatov R (2003) Proofreading tile sets: error correction for algorithmic self-assembly. In: Proceedings of the 9th International Workshop on DNA Based Computers, 126\u2013144"},{"key":"9048_CR38","doi-asserted-by":"crossref","first-page":"539","DOI":"10.1038\/28998","volume":"394","author":"E Winfree","year":"1998","unstructured":"Winfree E, Liu F, Wenzler LA, Seeman NC (1998) Design and self-assembly of two-dimensional DNA crystals. Nature 394:539\u2013544","journal-title":"Nature"},{"issue":"14","key":"9048_CR39","doi-asserted-by":"crossref","first-page":"8103","DOI":"10.1073\/pnas.1032954100","volume":"100","author":"H Yan","year":"2003","unstructured":"Yan H, LaBean TH, Feng L, Reif JH (2003) Directed nucleation assembly of DNA tile complexes for barcode-patterned lattices. Proc Natl Acad Sci USA 100(14):8103\u20138108","journal-title":"Proc Natl Acad Sci USA"}],"container-title":["Natural Computing"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s11047-007-9048-6.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s11047-007-9048-6\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s11047-007-9048-6","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,6,1]],"date-time":"2019-06-01T03:46:02Z","timestamp":1559360762000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s11047-007-9048-6"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2007,10,2]]},"references-count":39,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2008,6]]}},"alternative-id":["9048"],"URL":"https:\/\/doi.org\/10.1007\/s11047-007-9048-6","relation":{},"ISSN":["1567-7818","1572-9796"],"issn-type":[{"value":"1567-7818","type":"print"},{"value":"1572-9796","type":"electronic"}],"subject":[],"published":{"date-parts":[[2007,10,2]]}}}