Tile complexity of approximate squares

DOI10.1007/s00453-012-9620-zzbMath1262.68185OpenAlexW2018891418MaRDI 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 algorithmsself-assemblytile assembly modelprogram size complexity

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Protein sequences, DNA sequences (92D20) Approximation algorithms (68W25)

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