3-Color bounded patterned self-assembly (Extended abstract)

Lila Kari, Steffen Kopecki, Shinnosuke Seki

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

    1 Citation (Scopus)

    Abstract

    Patterned self-assembly tile set synthesis (Pats) is the problem of finding a minimal tile set which uniquely self-assembles into a given pattern. Czeizler and Popa proved the NP-completeness of Pats and Seki showed that the Pats problem is already NP-complete for patterns with 60 colors. In search for the minimal number of colors such that Pats remains NP-complete, we introduce multiple bound Pats (mbPats) where we allow bounds for the numbers of tile types of each color. We show that mbPats is NP-complete for patterns with just three colors and, as a byproduct of this result, we also obtain a novel proof for the NP-completeness of pats which is more concise than the previous proofs.

    Original languageEnglish
    Title of host publicationDNA Computing and Molecular Programming - 19th International Conference, DNA 2013, Proceedings
    Pages105-117
    Number of pages13
    Volume8141 LNCS
    DOIs
    Publication statusPublished - 2013
    MoE publication typeA4 Article in a conference publication
    EventInternational Conference on DNA Computing and Molecular Programming - Arizona State University, Tempe, United States
    Duration: 22 Sep 201327 Sep 2013
    Conference number: 19

    Publication series

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

    Conference

    ConferenceInternational Conference on DNA Computing and Molecular Programming
    Abbreviated titleDNA
    CountryUnited States
    CityTempe
    Period22/09/201327/09/2013

    Fingerprint Dive into the research topics of '3-Color bounded patterned self-assembly (Extended abstract)'. Together they form a unique fingerprint.

    Cite this