Tile complexity of approximate squares

DOI10.1007/s00453-012-9620-zzbMath1262.68185MaRDI QIDQ1949754

Nikhil Gopalkrishnan, Harish Chandran, John H. Reif

Publication date: 16 May 2013

Published in: Algorithmica (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00453-012-9620-z

zbMATH Keywords

approximation algorithms; self-assembly; tile assembly model; program size complexity

Mathematics Subject Classification ID

68Q25: Analysis of algorithms and problem complexity

92D20: Protein sequences, DNA sequences

68W25: Approximation algorithms

Related Items

Parallel Computation Using Active Self-assembly, Parallel computation using active self-assembly

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Limitations of self-assembly at temperature 1
• Staged self-assembly: nanomanufacture of arbitrary shapes with \(O(1)\) glues
• The program-size complexity of self-assembled squares (extended abstract)
• Randomized Self-assembly for Approximate Shapes
• Reducing tile complexity for self-assembly through temperature programming
• Programmable Control of Nucleation for Algorithmic Self-Assembly
• The Tile Complexity of Linear Assemblies
• Time Optimal Self-assembly for 2D and 3D Shapes: The Case of Squares and Cubes
• Running time and program size for self-assembled squares
• Complexities for Generalized Models of Self-Assembly
• Self-assemblying Classes of Shapes with a Minimum Number of Tiles, and in Optimal Time
• Randomized Self-Assembly for Exact Shapes
• DNA Computing
• DNA Computing
• The undecidability of the domino problem
• DNA Computing