Counting Polyominoes on Twisted Cylinders

Gill Barequet; Micha Moffie; Ares Ribó; Günter Rote

doi:10.46298/dmtcs.3446

Gill Barequet ; Micha Moffie ; Ares Ribó ; Günter Rote - Counting Polyominoes on Twisted Cylinders

dmtcs:3446 - Discrete Mathematics & Theoretical Computer Science, January 1, 2005, DMTCS Proceedings vol. AE, European Conference on Combinatorics, Graph Theory and Applications (EuroComb '05) - https://doi.org/10.46298/dmtcs.3446

Counting Polyominoes on Twisted CylindersConference paper

Authors: Gill Barequet ¹; Micha Moffie ¹; Ares Ribó ²; Günter Rote ²

1 Department of Computer Science [Haifa]
2 Institut für Informatik [Berlin]

We improve the lower bounds on Klarner's constant, which describes the exponential growth rate of the number of polyominoes (connected subsets of grid squares) with a given number of squares. We achieve this by analyzing polyominoes on a different surface, a so-called $\textit{twisted cylinder}$ by the transfer matrix method. A bijective representation of the "states'' of partial solutions is crucial for allowing a compact representation of the successive iteration vectors for the transfer matrix method.

https://doi.org/10.46298/dmtcs.3446

Source: HAL:hal-01184435v1

Volume: DMTCS Proceedings vol. AE, European Conference on Combinatorics, Graph Theory and Applications (EuroComb '05)

Section: Proceedings

Published on: January 1, 2005

Imported on: May 10, 2017

Keywords: [INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM], [MATH.MATH-CO]Mathematics [math]/Combinatorics [math.CO], [en] polyomino, combinatorial counting

Bibliographic References

26 Documents citing this article

Gill Barequet;Mira Shalah, 2020, Improved Upper Bounds on the Growth Constants of Polyominoes and Polycubes, Lecture notes in computer science, pp. 532-545, 10.1007/978-3-030-61792-9_42.

Gadi Aleksandrowicz;Andrei Asinowski;Gill Barequet;Ronnie Barequet, 2014, Formulae for Polyominoes on Twisted Cylinders, Lecture notes in computer science, pp. 76-87, 10.1007/978-3-319-04921-2_6.

Anelize Zomkowski Salvi;Roberto Simoni;Daniel Martins, 2012, Enumeration Problems: A Bridge Between Planar Metamorphic Robots in Engineering and Polyforms in Mathematics, Advances in Reconfigurable Mechanisms and Robots I, pp. 25-34, 10.1007/978-1-4471-4141-9_3.

2011, Figure Credits, The Nature of Computation, pp. xii-xiv, 10.1093/acprof:oso/9780199233212.002.0006.

2011, Dedication, The Nature of Computation, pp. v, 10.1093/acprof:oso/9780199233212.002.0004.

2011, Preface, The Nature of Computation, pp. xv-xvii, 10.1093/acprof:oso/9780199233212.002.0007.

2011, Mathematical Tools, The Nature of Computation, pp. 911-943, 10.1093/acprof:oso/9780199233212.005.0001.

Cristopher Moore;Stephan Mertens, 2011, Random Walks and Rapid Mixing, The Nature of Computation, pp. 563-650, 10.1093/acprof:oso/9780199233212.003.0012.

Cristopher Moore;Stephan Mertens, 2011, Needles in a Haystack: the Class NP, The Nature of Computation, pp. 94-126, 10.1093/acprof:oso/9780199233212.003.0004.

Cristopher Moore;Stephan Mertens, 2011, Who is the Hardest One of All? NP-Completeness, The Nature of Computation, pp. 127-172, 10.1093/acprof:oso/9780199233212.003.0005.

Cristopher Moore;Stephan Mertens, 2011, Memory, Paths, and Games, The Nature of Computation, pp. 300-330, 10.1093/acprof:oso/9780199233212.003.0008.

Cristopher Moore;Stephan Mertens, 2011, Randomized Algorithms, The Nature of Computation, pp. 450-505, 10.1093/acprof:oso/9780199233212.003.0010.

Cristopher Moore;Stephan Mertens, 2011, Counting, Sampling, and Statistical Physics, The Nature of Computation, pp. 651-665, 10.1093/acprof:oso/9780199233212.003.0013.

Cristopher Moore;Stephan Mertens, 2011, Optimization and Approximation, The Nature of Computation, pp. 351-449, 10.1093/acprof:oso/9780199233212.003.0009.

Cristopher Moore;Stephan Mertens, 2011, The Deep Question: P vs. NP, The Nature of Computation, pp. 173-212, 10.1093/acprof:oso/9780199233212.003.0006.

Cristopher Moore;Stephan Mertens, 2011, When Formulas Freeze: Phase Transitions in Computation, The Nature of Computation, pp. 723-818, 10.1093/acprof:oso/9780199233212.003.0014.

Cristopher Moore;Stephan Mertens, 2011, The Basics, The Nature of Computation, pp. 15-40, 10.1093/acprof:oso/9780199233212.003.0002.

Cristopher Moore;Stephan Mertens, 2011, Quantum Computation, The Nature of Computation, pp. 819-910, 10.1093/acprof:oso/9780199233212.003.0015.

Cristopher Moore;Stephan Mertens, 2011, Prologue, The Nature of Computation, pp. 1-14, 10.1093/acprof:oso/9780199233212.003.0001.

Cristopher Moore;Stephan Mertens, 2011, Insights and Algorithms, The Nature of Computation, pp. 41-93, 10.1093/acprof:oso/9780199233212.003.0003.

Cristopher Moore;Stephan Mertens, 2011, Interaction and Pseudorandomness, The Nature of Computation, pp. 506-562, 10.1093/acprof:oso/9780199233212.003.0011.

Cristopher Moore;Stephan Mertens, 2011, The Nature of Computation, CERN Document Server (European Organization for Nuclear Research), 10.1093/acprof:oso/9780199233212.001.0001.

Moore Cristopher, 2011, The Grand Unified Theory of Computation, The Nature of Computation, pp. 223-299, 10.1093/acprof:oso/9780199233212.003.0007.

Moore, Cristopher 1968-;Mertens, Stephan, 2011, Copyright Page, The Nature of Computation, pp. iv, 10.1093/acprof:oso/9780199233212.002.0003.

G. Castiglione;A. Frosini;E. Munarini;A. Restivo;S. Rinaldi, 2006, Combinatorial aspects of L-convex polyominoes, Nova Science Publishers (Nova Science Publishers, Inc.), 28, 6, pp. 1724-1741, 10.1016/j.ejc.2006.06.020, http://hdl.handle.net/10447/17789.

Gill Barequet;Micha Moffie, 2006, On the complexity of Jensen's algorithm for counting fixed polyominoes, Journal of Discrete Algorithms, 5, 2, pp. 348-355, 10.1016/j.jda.2005.08.001.

Sources : OpenCitations, OpenAlex & Crossref

Share and export

Consultation statistics

This page has been seen 404 times.

This article's PDF has been downloaded 419 times.