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

DOI10.1016/J.TCS.2010.10.034MaRDI QIDQ633697zbMATH OpenOpenAlexFDO

Authors J. Reif, Sudheer Sahu, Peng Yin

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)

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

Cites work

• scientific article; zbMATH DE number 610968 (Why is no real title available?)
• scientific article; zbMATH DE number 1953202 (Why is no real title available?)
• scientific article; zbMATH DE number 2065647 (Why is no real title available?)
• scientific article; zbMATH DE number 2152822 (Why is no real title available?)
• A Grammatical Approach to Self-Organizing Robotic Systems
• A Self-assembly Model of Time-Dependent Glue Strength
• Combinatorial optimization problems in self-assembly
• Complexities for generalized models of self-assembly
• Complexity of Compact Proofreading for Self-assembled Patterns
• DNA Computing
• DNA Computing
• DNA Computing
• DNA Computing
• DNA Computing
• DNA Computing
• Invadable self-assembly: combining robustness with efficiency
• Planar Formulae and Their Uses
• Programmable control of nucleation for algorithmic self-assembly
• Reducing tile complexity for self-assembly through temperature programming
• Running time and program size for self-assembled squares
• The program-size complexity of self-assembled squares (extended abstract)
• Unconventional Computation
• Undecidability and nonperiodicity for tilings of the plane

Cited in

(18)

• Self-assembly of any shape with constant tile types using high temperature
• Robust Self-assembly of Graphs
• The computational power of simple protocols for self-awareness on graphs
• Covert computation in self-assembled circuits
• A novel multi-agent model for chemical self-assembly
• Covert computation in self-assembled circuits
• Complexities for Generalized Models of Self-Assembly
• Multiset-based self-assembly of graphs
• Robust self-assembly of graphs
• Unconventional Computation
• On the complexity of graph self-assembly in accretive systems
• Identifying shapes using self-assembly
• Dipole codes attractively encode glue functions
• On aggregation in multiset-based self-assembly of graphs
• Self-Replicability of Composite Graph Reproduction System
• On the Complexity of Graph Self-assembly in Accretive Systems
• Simplifying the role of signals in tile self-assembly
• Complexity of Graph Self-assembly in Accretive Systems and Self-destructible Systems

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)