2009/11/16 by Mika Göös, Göös, Mika, Pekka Orponen +1 · 1 citation
Biochemistry, Genetics and Molecular Biology · Computer Science · Engineering · Mathematics · #Advanced biosensing and bioanalysis techniques #Algorithm #Artificial intelligence #Bounding overwatch #Branch and bound #Cardinality (data modeling) #Combinatorics #Computer science #DNA and Biological Computing #Data Structures and Algorithms (cs.DS) #Data mining #F.1.1 #F.2.2 #FOS: Computer and information sciences #Function (biology) #G.2.1 #Grid #Heuristic #J.2 #Mathematical optimization #Mathematics #Modular Robots and Swarm Intelligence #Rectangle #Set (abstract data type) #Tile #cs.DS
paper · pdf · doi:10.48550/arxiv.0911.2924
12 pages, 6 figures
openalex publication_date 2009/11/16 · arxiv created 2010/08/14 · arxiv updated 2015/03/13 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/05
The Pattern self-Assembly Tile set Synthesis (PATS) problem is to determine a set of coloured tiles that self-assemble to implement a given rectangular colour pattern. We give an exhaustive branch-and-bound algorithm to find tile sets of minimum cardinality for the PATS problem. Our algorithm makes use of a search tree in the lattice of partitions of the ambient rectangular grid, and an efficient bounding function to prune this search tree. Empirical data on the performance of the algorithm shows that it compares favourably to previously presented heuristic solutions to the problem.