A manually-checkable proof for the NP-hardness of 11-color pattern self-assembly tileset synthesis
From MaRDI portal
Publication:511695
DOI10.1007/S10878-015-9975-6zbMath1361.90050arXiv1409.1619OpenAlexW1484881446MaRDI QIDQ511695
Shinnosuke Seki, Aleck Johnsen, Ming-Yang Kao
Publication date: 22 February 2017
Published in: Journal of Combinatorial Optimization (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1409.1619
Related Items (3)
Binary pattern tile set synthesis is NP-hard ⋮ 3-color bounded patterned self-assembly ⋮ The Complexity of Fixed-Height Patterned Tile Self-assembly
Cites Work
- Unnamed Item
- 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
- Binary pattern tile set synthesis is NP-hard
- Solving NP-complete problems in the tile assembly model
- Efficient 3-SAT algorithms in the tile assembly model
- Computing Minimum Tile Sets to Self-Assemble Color Patterns
- Solving satisfiability in the tile assembly model with a constant-size tileset
- 3-Color Bounded Patterned Self-assembly
- Combinatorial Optimization in Pattern Assembly
- The complexity of satisfiability problems
- DNA Computing
This page was built for publication: A manually-checkable proof for the NP-hardness of 11-color pattern self-assembly tileset synthesis
