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

DOI10.1016/J.TCS.2010.10.034zbMATH Open1237.68103OpenAlexW1973868833MaRDI QIDQ633697FDOQ633697

Peng Yin, Sudheer Sahu, J. 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

graphcomplexityDNANP-completeself-assemblyPSPACE-completeNPnanostrcture

Mathematics Subject Classification ID

Genetics and epigenetics (92D10) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10)

Cites Work

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

Cited In (13)

• The computational power of simple protocols for self-awareness on graphs
• Complexities for Generalized Models of Self-Assembly
• Robust self-assembly of graphs
• Identifying shapes using self-assembly
• Negative interactions in irreversible self-assembly
• Title not available (Why is that?)
• Simplifying the role of signals in tile self-assembly
• Covert computation in self-assembled circuits
• Robust Self-assembly of Graphs
• Self-assembly of shapes at constant scale using repulsive forces
• Self-Replicability of Composite Graph Reproduction System
• Title not available (Why is that?)
• Dipole codes attractively encode glue functions

   Recommendations

• Complexity of Graph Self-assembly in Accretive Systems and Self-destructible Systems 👍 👎
• On the complexity of graph self-assembly in accretive systems 👍 👎
• On the Complexity of Graph Self-assembly in Accretive Systems 👍 👎
• Robust self-assembly of graphs 👍 👎
• Robust Self-assembly of Graphs 👍 👎

This page was built for publication: Complexity of graph self-assembly in accretive systems and self-destructible systems

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q633697)