Appel, K. and Haken, W. Every planar map is four colorable. Illinois Journal of Mathematics 21, 3 (Sept. 1977), 429--490 (part I) and 491--567 (part II).

Google Scholar

[2]

Avigad, J. and Harrison, J. Formally verified mathematics. Commun. ACM 57, 4 (April 2014), 66--75.

Digital Library

Google Scholar

[3]

Aleksandrowicz, G., Asinowski, A., Barequet, G., and Barequet, R. Formulae for polyominoes on twisted cylinders. In Proceedings of the Eighth International Conference on Language and Automata Theory and Applications, Lecture Notes in Computer Science 8370 (Madrid, Spain, Mar. 10-14). Springer-Verlag, Heidelberg, New York, Dordrecht, London, 2014, 76--87.

Google Scholar

[4]

Barequet, G. and Moffie, M. On the complexity of Jensen's algorithm for counting fixed polyominoes. Journal of Discrete Algorithms 5, 2 (June 2007), 348--355.

Digital Library

Google Scholar

[5]

Barequet, G., Moffie, M., Ribó, A., and Rote, G. Counting polyominoes on twisted cylinders. INTEGERS: Electronic Journal of Combinatorial Number Theory 6 (Sept. 2006), #A22, 37.

Google Scholar

[6]

Barequet, G., Rote, G., and Shalah, M. λ > 4. In Proceedings of the 23^rd Annual European Symposium on Algorithms Lecture Notes in Computer Science 9294 (Patras, Greece, Sept. 14-16). Springer-Verlag, Berlin Heidelberg, Germany, 2015, 83--94.

Google Scholar

[7]

Barequet, G. and Shalah, M. Polyominoes on twisted cylinders. In the Video Review at the 29^th Annual Symposium on Computational Geometry (Rio de Janeiro, Brazil, June 17-20). ACM Press, New York, 2013, 339--340; http://www.computational-geometry.org/SoCG-videos/socg13video

Digital Library

Google Scholar

[8]

Broadbent, S.R. and Hammersley, J.M. Percolation processes: I. Crystals and mazes. Proceedings of the Cambridge Philosophical Society 53, 3 (July 1957), 629--641.

Crossref

Google Scholar

[9]

Conway, A. Enumerating 2D percolation series by the finite-lattice method: Theory. Journal of Physics, A: Mathematical and General 28, 2 (Jan. 1995), 335--349.

Google Scholar

[10]

Derrida, B. and Herrmann, H.J. Collapse of branched polymers. Journal de Physique 44, 12 (Dec. 1983), 1365--1376.

Crossref

Google Scholar

[11]

Flesia, S., Gaunt, D.S., Soteros, C.E., and Whittington, S.G. Statistics of collapsing lattice animals. Journal of Physics, A: Mathematical and General 27, 17 (Sept. 1994), 5831--5846.

Google Scholar

[12]

Gaunt, D.S., Sykes, M.F., and Ruskin, H. Percolation processes in d-dimensions. Journal of Physics A: Mathematical and General 9, 11 (Nov. 1976), 1899--1911.

Google Scholar

[13]

Golomb, S.W. Polyominoes, Second Edition. Princeton University Press, Princeton, NJ, 1994.

Google Scholar

[14]

Gonthier, G. Formal proof---The four color theorem. Notices of the AMS 55, 11 (Dec. 2008), 1382--1393.

Google Scholar

[15]

Guttmann, A.J., Ed. Polygons, Polyominoes and Polycubes, Lecture Notes in Physics 775. Springer, Heidelberg, Germany, 2009.

Digital Library

Google Scholar

[16]

Hales, T., Solovyev, A., and Le Truong, H. The Flyspeck Project: Announcement of Completion, Aug. 10, 2014; https://code.google.com/p/fyspeck/wiki/AnnouncingCompletion

Google Scholar

[17]

Hopcroft, J.E. and Tarjan, R.E. Dividing a graph into triconnected components. SIAM Journal of Computing 2, 3 (Sept. 1973), 135--158.

Crossref

Google Scholar

[18]

Jensen, I. Counting polyominoes: A parallel implementation for cluster computing. In Proceedings of the International Conference on Computational Science, Part III, Lecture Notes in Computer Science, 2659 (Melbourne, Australia, and St. Petersburg, Russian Federation, June 2-4). Springer-Verlag, Berlin, Heidelberg, New York, 2003, 203--212.

Digital Library

Google Scholar

[19]

Klarner, D.A. Cell growth problems. Canadian Journal of Mathematics 19, 4 (1967), 851--863.

Crossref

Google Scholar

[20]

Klarner, D.A. and Rivest, R.L. A procedure for improving the upper bound for the number of n-ominoes. Canadian Journal of Mathematics 25, 3 (Jan. 1973), 585--602.

Crossref

Google Scholar

[21]

Lagarias, J.C., Ed. The Kepler Conjecture: The Hales-Ferguson Proof. Springer, New York, 2011.

Crossref

Google Scholar

[22]

Lubensky, T.C. and Isaacson, J. Statistics of lattice animals and dilute branched polymers. Physical Review A 20, 5 (Nov. 1979), 2130--2146.

Crossref

Google Scholar

[23]

Madras, N. A pattern theorem for lattice clusters. Annals of Combinatorics 3, 2-4 (June 1999), 357--384.

Crossref

Google Scholar

[24]

Madras, N., Soteros, C.E., Whittington, S.G., Martin, J.L., Sykes, M.F., Flesia, S., and Gaunt, D.S. The free energy of a collapsing branched polymer. Journal of Physics, A: Mathematical and General 23, 22 (Nov. 1990), 5327--5350.

Google Scholar

[25]

McConnell, R.M., Mehlhorn, K., Näher, S., and Schweitzer, P. Certifying algorithms. Computer Science Review 5, 2 (May 2011), 119--161.

Digital Library

Google Scholar

[26]

Mertens, S. and Lautenbacher, M.E. Counting lattice animals: A parallel attack. Journal of Statistical Physics 66, 1--2 (Jan. 1992), 669--678.

Crossref

Google Scholar

[27]

Redelmeier, D.H. Counting polyominoes: Yet another attack. Discrete Mathematics 36, 3 (Dec. 1981), 191--203.

Digital Library

Google Scholar

[28]

Schmidt, J.M. Contractions, removals and certifying 3-connectivity in linear time, SIAM Journal on Computing 42, 2 (Mar. 2013), 494--535.

Crossref

Google Scholar

[29]

Sykes, M.F. and Glen, M. Percolation processes in two dimensions: I. Low-density series expansions. Journal of Physics, A: Mathematical and General 9, 1 (Jan. 1976), 87--95.

Google Scholar

[30]

Tucker, W. A rigorous ODE solver and Smale's 14^th problem. Foundations of Computational Mathematics 2, 1 (Jan. 2002), 53--117.

Digital Library

Google Scholar

Cited By

View all

Bui V(2025)Bounding Klarner’s constant from above using a simple recurrenceArchiv der Mathematik10.1007/s00013-024-02099-2Online publication date: 26-Feb-2025
https://doi.org/10.1007/s00013-024-02099-2
Mansour T(2024)Smooth squared, triangular, and hexagonal bargraphsApplicable Analysis and Discrete Mathematics10.2298/AADM220603003M18:1(215-228)Online publication date: 2024
https://doi.org/10.2298/AADM220603003M
Berg MKamali SLing KSigrist C(2024)Space-Efficient Data Structures for Polyominoes and Bar Graphs2024 Data Compression Conference (DCC)10.1109/DCC58796.2024.00033(253-262)Online publication date: 19-Mar-2024
https://doi.org/10.1109/DCC58796.2024.00033
Show More Cited By

Index Terms

λ > 4: an improved lower bound on the growth constant of polyominoes

Recommendations

A Tight Runtime Analysis of the (1+(λ, λ)) Genetic Algorithm on OneMax
GECCO '15: Proceedings of the 2015 Annual Conference on Genetic and Evolutionary Computation

Understanding how crossover works is still one of the big challenges in evolutionary computation research, and making our understanding precise and proven by mathematical means might be an even bigger one. As one of few examples where crossover provably ...
Algorithms for testing occurrences of length 4 patterns in permutations

In this paper linear time sequential and optimal parallel algorithms for testing pattern involvement for all length 4 permutations are described. This is an improvement as the previous best sequential algorithms, for most of these pattern require $$O(n\...
Password book vol.4: Internet, Web Site Password Keeper/Directory Modern Password Keeper, Vault, Notebook and Online Organizer. Logbook With 240 places To Record Passwords. 82 pages (Volume 4)

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

Communications of the ACM Volume 59, Issue 7

July 2016

118 pages

ISSN:0001-0782

EISSN:1557-7317

DOI:10.1145/2963119

Editor:
Moshe Y. Vardi
Association for Computing Machinery, New York, NY

Issue’s Table of Contents

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 24 June 2016

Published in CACM Volume 59, Issue 7

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Research-article
Popular
Refereed

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

26
Total Citations
View Citations
1,342
Total Downloads

Downloads (Last 12 months)210
Downloads (Last 6 weeks)21

Reflects downloads up to 28 Feb 2025

Other Metrics

View Author Metrics

Citations

Cited By

View all

Bui V(2025)Bounding Klarner’s constant from above using a simple recurrenceArchiv der Mathematik10.1007/s00013-024-02099-2Online publication date: 26-Feb-2025
https://doi.org/10.1007/s00013-024-02099-2
Mansour T(2024)Smooth squared, triangular, and hexagonal bargraphsApplicable Analysis and Discrete Mathematics10.2298/AADM220603003M18:1(215-228)Online publication date: 2024
https://doi.org/10.2298/AADM220603003M
Berg MKamali SLing KSigrist C(2024)Space-Efficient Data Structures for Polyominoes and Bar Graphs2024 Data Compression Conference (DCC)10.1109/DCC58796.2024.00033(253-262)Online publication date: 19-Mar-2024
https://doi.org/10.1109/DCC58796.2024.00033
Defant CKravitz N(2024)Loops and regions in Hitomezashi patternsDiscrete Mathematics10.1016/j.disc.2023.113693347:1(113693)Online publication date: Jan-2024
https://doi.org/10.1016/j.disc.2023.113693
Barequet GMagal B(2023)Automatic generation of formulae for polyominoes with a fixed perimeter defectComputational Geometry: Theory and Applications10.1016/j.comgeo.2022.101919108:COnline publication date: 1-Jan-2023
https://dl.acm.org/doi/10.1016/j.comgeo.2022.101919
Bui V(2023)An Asymptotic Lower Bound on the Number of PolyominoesAnnals of Combinatorics10.1007/s00026-023-00675-xOnline publication date: 21-Dec-2023
https://doi.org/10.1007/s00026-023-00675-x
Barequet GBen-Shachar G(2022)Algorithms for Counting Minimum-Perimeter Lattice AnimalsAlgorithmica10.1007/s00453-022-01008-985:1(75-99)Online publication date: 4-Aug-2022
https://dl.acm.org/doi/10.1007/s00453-022-01008-9
Barequet GShalah M(2022)Improved Upper Bounds on the Growth Constants of Polyominoes and PolycubesAlgorithmica10.1007/s00453-022-00948-684:12(3559-3586)Online publication date: 1-Dec-2022
https://dl.acm.org/doi/10.1007/s00453-022-00948-6
Asinowski ABarequet GZheng Y(2022)Polycubes with Small Perimeter DefectAnnals of Combinatorics10.1007/s00026-022-00601-726:4(997-1020)Online publication date: 10-Sep-2022
https://doi.org/10.1007/s00026-022-00601-7
Lu YBhattacharjee ABiediger DKim MBecker A(2021)Enumeration of Polyominoes & Polycubes Composed of Magnetic Cubes2021 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS)10.1109/IROS51168.2021.9636784(6977-6982)Online publication date: 27-Sep-2021
https://dl.acm.org/doi/10.1109/IROS51168.2021.9636784
Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Digital Edition

View this article in digital edition.

Digital Edition

Magazine Site

View this article on the magazine site (external)

Magazine Site

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Abstract

Supplementary Material

References

Cited By

Index Terms

Recommendations

A Tight Runtime Analysis of the (1+(λ, λ)) Genetic Algorithm on OneMax

Algorithms for testing occurrences of length 4 patterns in permutations

Password book vol.4: Internet, Web Site Password Keeper/Directory Modern Password Keeper, Vault, Notebook and Online Organizer. Logbook With 240 places To Record Passwords. 82 pages (Volume 4)

Comments

Information

Published In

Publisher

Publication History

Permissions

Check for updates

Qualifiers

Contributors

Other Metrics

Bibliometrics

Article Metrics

Other Metrics

Citations

Cited By

View options

PDF

eReader

Digital Edition

Magazine Site

Login options

Full Access

Share

Share this Publication link

Share on social media

Affiliations