Complexity of Graph Self-assembly in Accretive Systems and Self-destructible Systems

DOI10.1007/11753681_21zbMath1234.68142MaRDI QIDQ3618692

Sudheer Sahu, Peng Yin, John H. Reif

Publication date: 2 April 2009

Published in: DNA Computing (Search for Journal in Brave)

Full work available at URL: http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.300.4078

Mathematics Subject Classification ID

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

68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)

Related Items

Exponential Replication of Patterns in the Signal Tile Assembly Model, Geometric tiles and powers and limitations of geometric hindrance in self-assembly, An introduction to tile-based self-assembly and a survey of recent results, Growing self-organizing trees for autonomous hierarchical clustering, Optimization of supply diversity for the self-assembly of simple objects in two and three dimensions, Negative interactions in irreversible self-assembly, Exponential replication of patterns in the signal tile assembly model, Hierarchical self assembly of patterns from the Robinson tilings: DNA tile design in an enhanced tile assembly model, Less Haste, Less Waste: On Recycling and Its Limits in Strand Displacement Systems, Exact Shapes and Turing Universality at Temperature 1 with a Single Negative Glue, A Self-assembly Model of Time-Dependent Glue Strength, Robust Self-assembly of Graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Self-assembling DNA graphs
• 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
• Assembly and Disassembly of Viral Capsids