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

DOI10.1007/11753681_21zbMath1234.68142OpenAlexW2130662633MaRDI 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

Graph theory (including graph drawing) in computer science (68R10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Related Items

Hierarchical self assembly of patterns from the Robinson tilings: DNA tile design in an enhanced tile assembly model ⋮ Negative interactions in irreversible self-assembly ⋮ Growing self-organizing trees for autonomous hierarchical clustering ⋮ Exponential Replication of Patterns in the Signal Tile Assembly Model ⋮ Exponential replication of patterns in the signal tile assembly model ⋮ Optimization of supply diversity for the self-assembly of simple objects in two and three dimensions ⋮ Geometric tiles and powers and limitations of geometric hindrance in self-assembly ⋮ A Self-assembly Model of Time-Dependent Glue Strength ⋮ 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 ⋮ Robust Self-assembly of Graphs ⋮ An introduction to tile-based self-assembly and a survey of recent results

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