Combinatorial optimization in pattern assembly (Extended Abstract)

Shinnosuke Seki*

*Corresponding author for this work

Research output: Chapter in Book/Report/Conference proceedingConference contributionScientificpeer-review

10 Citations (Scopus)

Abstract

Pattern self-assembly tile set synthesis (Pats) is an NP-hard combinatorial problem to minimize a rectilinear tile assembly system (RTAS) that uniquely self-assembles a given rectangular pattern. For c ≥ 1, c-Pats is a subproblem of Pats which takes only the patterns with at most c colors as input. We propose a polynomial-time reduction of 3Sat to 60-Pats in order to prove that 60-Pats is NP-hard.

Original languageEnglish
Title of host publicationUnconventional Computation and Natural Computation - 12th International Conference, UCNC 2013, Proceedings
Pages220-231
Number of pages12
Volume7956 LNCS
DOIs
Publication statusPublished - 2013
MoE publication typeA4 Article in a conference publication
EventInternational Conference on Unconventional Computation and Natural Computation - Universita degli Studi di Milano-Bicocca, Milan, Italy
Duration: 1 Jul 20135 Jul 2013
Conference number: 12

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume7956 LNCS
ISSN (Print)03029743
ISSN (Electronic)16113349

Conference

ConferenceInternational Conference on Unconventional Computation and Natural Computation
Abbreviated titleUCNC
CountryItaly
CityMilan
Period01/07/201305/07/2013

Fingerprint Dive into the research topics of 'Combinatorial optimization in pattern assembly (Extended Abstract)'. Together they form a unique fingerprint.

Cite this