Complexity of graph self-assembly in accretive systems and self-destructible systems

DOI10.1016/j.tcs.2010.10.034zbMath1237.68103MaRDI QIDQ633697

Peng Yin, Sudheer Sahu, John H. Reif

Publication date: 29 March 2011

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2010.10.034

zbMATH Keywords

complexity; graph; DNA; NP-complete; self-assembly; PSPACE-complete; NP; nanostrcture

Mathematics Subject Classification ID

68Q25: Analysis of algorithms and problem complexity

68R10: Graph theory (including graph drawing) in computer science

92D10: Genetics and epigenetics

Related Items

Unnamed Item, Unnamed Item, Simplifying the role of signals in tile self-assembly, Dipole codes attractively encode glue functions, Identifying shapes using self-assembly, Negative interactions in irreversible self-assembly, Self-assembly of shapes at constant scale using repulsive forces, Covert computation in self-assembled circuits

Cites Work

• Undecidability and nonperiodicity for tilings of the plane
• The program-size complexity of self-assembled squares (extended abstract)
• Combinatorial optimization problems in self-assembly
• Reducing tile complexity for self-assembly through temperature programming
• Programmable Control of Nucleation for Algorithmic Self-Assembly
• A Self-assembly Model of Time-Dependent Glue Strength
• Complexity of Compact Proofreading for Self-assembled Patterns
• Planar Formulae and Their Uses
• Running time and program size for self-assembled squares
• A Grammatical Approach to Self-Organizing Robotic Systems
• Unconventional Computation
• DNA Computing
• DNA Computing
• DNA Computing
• DNA Computing
• DNA Computing
• DNA Computing
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item