Skip to main contentSkip to search
Episciences
Open Access Journals
Sign in(new window)
Discrete Mathematics & Theoretical Computer Science logo
Discrete Mathematics & Theoretical Computer Science
Discrete Mathematics & Theoretical Computer Science logo
Discrete Mathematics & Theoretical Computer Science
Sign in(new window)
Articles & Issues
All articlesAll accepted articlesAll volumesLast volumeSectionsSpecial issuesAuthors
About
The journalIndexing
Boards
Publish
For authorsEthical charter
Submit
Discrete Mathematics & Theoretical Computer Science logo
Contact
|
Credits
eISSN 1365-8050
|
RSS
|
Atom
Episciences
Documentation
|
Acknowledgements
|
Publishing policy
Accessibility: non-compliant
|
Legal mentions
|
Privacy statement
|
Terms of use
  1. Home > Articles & Issues >
  2. Articles >
  3. Counting Polyominoes ...
Conference paper

Counting Polyominoes on Twisted Cylinders

Gill Barequet (1), Micha Moffie (1), Ares Ribó (2), Günter Rote ORCID (2)
(1) Department of Computer Science [Haifa]
(2) Institut für Informatik [Berlin]
Download article
Open on HAL
Imported on
May 10, 2017
Published on
December 31, 2004
Last modified on
March 31, 2025
Volume 0
DMTCS Proceedings vol. AE, European Conference on Combinatorics, Graph Theory and Applications (EuroComb '05)
Proceedings
DOI
10.46298/dmtcs.3446
License
https://about.hal.science/hal-authorisation-v1
Indicators
653
Views
766
Downloads

Counting Polyominoes on Twisted Cylinders

Gill Barequet (1), Micha Moffie (1), Ares Ribó (2), Günter Rote ORCID (2)
(1) Department of Computer Science [Haifa]
(2) Institut für Informatik [Berlin]
Abstract
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.
Keywords
  • [INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM]
  • [MATH.MATH-CO]Mathematics [math]/Combinatorics [math.CO]
  • polyomino
  • combinatorial counting
Cited by

Source: OpenCitations

  • On the complexity of Jensen's algorithm for counting fixed polyominoes

    Journal of Discrete Algorithms

    Authors : Gill Barequet ORCID, Micha Moffie

    Journal reference : Volume 5, 2006, pp. 348-355

    DOI : 10.1016/j.jda.2005.08.001

  • Who is the Hardest One of All? NP-Completeness

    The Nature of Computation

    Authors : Cristopher Moore ORCID, Stephan Mertens ORCID

    Journal reference : Volume , 2011, pp. 127-172

    DOI : 10.1093/acprof:oso/9780199233212.003.0005

  • Copyright Page

    The Nature of Computation

    Authors : Moore, Mertens

    Journal reference : Volume , 2011, pp. iv

    DOI : 10.1093/acprof:oso/9780199233212.002.0003

  • Interaction and Pseudorandomness

    The Nature of Computation

    Authors : Cristopher Moore ORCID, Stephan Mertens ORCID

    Journal reference : Volume , 2011, pp. 506-562

    DOI : 10.1093/acprof:oso/9780199233212.003.0011

  • Preface

    The Nature of Computation

    Authors :

    Journal reference : Volume , 2011, pp. xv-xvii

    DOI : 10.1093/acprof:oso/9780199233212.002.0007

  • Figure Credits

    The Nature of Computation

    Authors :

    Journal reference : Volume , 2011, pp. xii-xiv

    DOI : 10.1093/acprof:oso/9780199233212.002.0006

  • Memory, Paths, and Games

    The Nature of Computation

    Authors : Cristopher Moore ORCID, Stephan Mertens ORCID

    Journal reference : Volume , 2011, pp. 300-330

    DOI : 10.1093/acprof:oso/9780199233212.003.0008

  • The Basics

    The Nature of Computation

    Authors : Cristopher Moore ORCID, Stephan Mertens ORCID

    Journal reference : Volume , 2011, pp. 15-40

    DOI : 10.1093/acprof:oso/9780199233212.003.0002

  • Counting, Sampling, and Statistical Physics

    The Nature of Computation

    Authors : Cristopher Moore ORCID, Stephan Mertens ORCID

    Journal reference : Volume , 2011, pp. 651-665

    DOI : 10.1093/acprof:oso/9780199233212.003.0013

  • Dedication

    The Nature of Computation

    Authors :

    Journal reference : Volume , 2011, pp. v

    DOI : 10.1093/acprof:oso/9780199233212.002.0004

  • When Formulas Freeze: Phase Transitions in Computation

    The Nature of Computation

    Authors : Cristopher Moore ORCID, Stephan Mertens ORCID

    Journal reference : Volume , 2011, pp. 723-818

    DOI : 10.1093/acprof:oso/9780199233212.003.0014

  • Enumeration Problems: A Bridge Between Planar Metamorphic Robots in Engineering and Polyforms in Mathematics

    Advances in Reconfigurable Mechanisms and Robots I

    Authors : Anelize Zomkowski Salvi ORCID, Roberto Simoni ORCID, Daniel Martins ORCID

    Journal reference : Volume , 2012, pp. 25-34

    DOI : 10.1007/978-1-4471-4141-9_3

  • Random Walks and Rapid Mixing

    The Nature of Computation

    Authors : Cristopher Moore ORCID, Stephan Mertens ORCID

    Journal reference : Volume , 2011, pp. 563-650

    DOI : 10.1093/acprof:oso/9780199233212.003.0012

  • The Deep Question: P vs. NP

    The Nature of Computation

    Authors : Cristopher Moore ORCID, Stephan Mertens ORCID

    Journal reference : Volume , 2011, pp. 173-212

    DOI : 10.1093/acprof:oso/9780199233212.003.0006

  • Improved Upper Bounds on the Growth Constants of Polyominoes and Polycubes

    Lecture notes in computer science

    Authors : Gill Barequet ORCID, Mira Shalah

    Journal reference : Volume , 2020, pp. 532-545

    DOI : 10.1007/978-3-030-61792-9_42

  • Needles in a Haystack: the Class NP

    The Nature of Computation

    Authors : Cristopher Moore ORCID, Stephan Mertens ORCID

    Journal reference : Volume , 2011, pp. 94-126

    DOI : 10.1093/acprof:oso/9780199233212.003.0004

  • Mathematical Tools

    The Nature of Computation

    Authors :

    Journal reference : Volume , 2011, pp. 911-943

    DOI : 10.1093/acprof:oso/9780199233212.005.0001

  • Formulae for Polyominoes on Twisted Cylinders

    Lecture notes in computer science

    Authors : Gadi Aleksandrowicz, Andrei Asinowski ORCID, Gill Barequet ORCID, Ronnie Barequet

    Journal reference : Volume , 2014, pp. 76-87

    DOI : 10.1007/978-3-319-04921-2_6

  • The Grand Unified Theory of Computation

    The Nature of Computation

    Authors : Moore Cristopher

    Journal reference : Volume , 2011, pp. 223-299

    DOI : 10.1093/acprof:oso/9780199233212.003.0007

  • Quantum Computation

    The Nature of Computation

    Authors : Cristopher Moore ORCID, Stephan Mertens ORCID

    Journal reference : Volume , 2011, pp. 819-910

    DOI : 10.1093/acprof:oso/9780199233212.003.0015

  • Combinatorial aspects of L -convex polyominoes

    European Journal of Combinatorics

    Authors : G. Castiglione ORCID, A. Frosini ORCID, E. Munarini ORCID, A. Restivo ORCID, S. Rinaldi

    Journal reference : Volume 28, 2006, pp. 1724-1741

    DOI : 10.1016/j.ejc.2006.06.020

  • Randomized Algorithms

    The Nature of Computation

    Authors : Cristopher Moore ORCID, Stephan Mertens ORCID

    Journal reference : Volume , 2011, pp. 450-505

    DOI : 10.1093/acprof:oso/9780199233212.003.0010

  • Prologue

    The Nature of Computation

    Authors : Cristopher Moore ORCID, Stephan Mertens ORCID

    Journal reference : Volume , 2011, pp. 1-14

    DOI : 10.1093/acprof:oso/9780199233212.003.0001

  • Optimization and Approximation

    The Nature of Computation

    Authors : Cristopher Moore ORCID, Stephan Mertens ORCID

    Journal reference : Volume , 2011, pp. 351-449

    DOI : 10.1093/acprof:oso/9780199233212.003.0009

  • The Nature of Computation

    International Linear Collider

    Authors : Cristopher Moore ORCID, Stephan Mertens ORCID

    Journal reference : Volume , 2011, pp.

    DOI : 10.1093/acprof:oso/9780199233212.001.0001

  • Insights and Algorithms

    The Nature of Computation

    Authors : Cristopher Moore ORCID, Stephan Mertens ORCID

    Journal reference : Volume , 2011, pp. 41-93

    DOI : 10.1093/acprof:oso/9780199233212.003.0003
Preview
Loading PDF preview...