Tile complexity of approximate squares

DOI10.1007/S00453-012-9620-ZMaRDI QIDQ1949754zbMATH OpenOpenAlexFDO

Authors Harish Chandran, Nikhil Gopalkrishnan, J. 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 algorithmstile assembly modelself-assemblyprogram size complexity

Mathematics Subject Classification ID

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

Recommendations

• Tile Complexity of Linear Assemblies
• Aspects of a multivariate complexity analysis for rectangle tiling
• Complexity of tile rotation problems
• A PTAS for the square tiling problem
• The Tile Complexity of Linear Assemblies
• Tiling of rectangles with squares and related problems via Diophantine approximation
• The complexity of generalized domino tilings
• Tiling with Squares and Packing Dominos in Polynomial Time
• Polyhedron approximation of tile set

Cites work

• scientific article; zbMATH DE number 3727583 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 1241374 (Why is no real title available?)
• Complexities for Generalized Models of Self-Assembly
• DNA Computing
• DNA Computing
• DNA Computing
• Limitations of self-assembly at temperature 1
• Programmable control of nucleation for algorithmic self-assembly
• Randomized Self-assembly for Approximate Shapes
• Randomized self-assembly for exact shapes
• Reducing tile complexity for self-assembly through temperature programming
• Running time and program size for self-assembled squares
• Self-assemblying Classes of Shapes with a Minimum Number of Tiles, and in Optimal Time
• Staged self-assembly: nanomanufacture of arbitrary shapes with \(O(1)\) glues
• The Tile Complexity of Linear Assemblies
• The program-size complexity of self-assembled squares (extended abstract)
• The undecidability of the domino problem
• Time Optimal Self-assembly for 2D and 3D Shapes: The Case of Squares and Cubes

Cited in

(8)

• High Complexity Tilings with Sparse Errors
• Program size and temperature in self-assembly
• Aspects of a multivariate complexity analysis for rectangle tiling
• Randomized self-assembly for exact shapes
• Tile Complexity of Linear Assemblies
• Randomized Self-assembly for Approximate Shapes
• Parallel Computation Using Active Self-assembly
• Parallel computation using active self-assembly

This page was built for publication: Tile complexity of approximate squares

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