Counting polyominoes: A parallel implementation for cluster computing

Research output: Contribution to journalArticle

38 Citations (Scopus)

Abstract

The exact enumeration of most interesting combinatorial problems has exponential computational complexity. The finite-lattice method reduces this complexity for most two-dimensional problems. The basic idea is to enumerate the problem on small finite lattices using a transfer-matrix formalism. Systematically grow the size of the lattices and combine the results in order to obtain the desired series for the infinite lattice limit. We have developed a parallel algorithm for the enumeration of polyominoes, which are connected sets of lattice cells joined at an edge. The algorithm implements the finite-lattice method and associated transfer-matrix calculations in a very efficient parallel setup. Test runs of the algorithm on a HP server cluster indicates that in this environment the algorithm scales perfectly from 2 to 64 processors.

Original languageEnglish
Pages (from-to)203-212
Number of pages10
JournalLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume2659
DOIs
Publication statusPublished - 18 Jun 2003
Externally publishedYes

Fingerprint Dive into the research topics of 'Counting polyominoes: A parallel implementation for cluster computing'. Together they form a unique fingerprint.

Cite this