Computing minimum tile sets to self-assemble color patterns

DOI10.1007/978-3-642-45030-3_65MaRDI QIDQ2872134zbMATH OpenOpenAlexFDO

Authors Aleck Johnsen, Shinnosuke Seki, Ming-Yang Kao

Publication date 14 January 2014

Published in Algorithms and Computation (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1404.2962

Mathematics Subject Classification ID

Erd?s problems and related topics of discrete geometry (52C10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05)

Abstract: Patterned self-assembly tile set synthesis (PATS) aims at finding a minimum tile set to uniquely self-assemble a given rectangular color pattern. For $kge1$, $k$-PATS is a variant of PATS that restricts input patterns to those with at most $k$ colors. We prove the {�f NP}-hardness of 29-PATS, where the best known is that of 60-PATS.

Recommendations

• Synthesizing minimal tile sets for complex patterns in the framework of patterned DNA self-assembly
• Combinatorial Optimization in Pattern Assembly
• 3-color bounded patterned self-assembly (extended abstract)
• 3-color bounded patterned self-assembly
• Synthesizing minimal tile sets for complex patterns in the framework of patterned DNA self-assembly

Cited in

(7)

• 3-color bounded patterned self-assembly
• Synthesizing small and reliable tile sets for patterned DNA self-assembly
• Synthesizing minimal tile sets for complex patterns in the framework of patterned DNA self-assembly
• Search methods for tile sets in patterned DNA self-assembly
• A manually-checkable proof for the NP-hardness of 11-color pattern self-assembly tileset synthesis
• 3-color bounded patterned self-assembly (extended abstract)
• Synthesizing minimal tile sets for complex patterns in the framework of patterned DNA self-assembly

This page was built for publication: Computing minimum tile sets to self-assemble color patterns

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