Beichl, I.
, O'Leary, D.
and Sullivan, F.
(2001),
Approximating the Number of Monomer-Dimer Coverings in Periodic Lattices, Physical Review E (Statistical, Nonlinear, and Soft Matter Physics), [online], https://tsapps.nist.gov/publication/get_pdf.cfm?pub_id=150809
(Accessed July 26, 2024)
Official websites use .gov
A .gov website belongs to an official government organization in the United States.
Secure .gov websites use HTTPS
A lock (
) or https:// means you’ve safely connected to the .gov website. Share sensitive information only on official, secure websites.
Approximating the Number of Monomer-Dimer Coverings in Periodic Lattices
Published
Author(s)
, ,
Abstract
Our starting point is an algorithm of Kenyon, Randall, and Sinclair, which built upon the ideas of Jerrum and Sinclair, giving an approximation to crucial parameters of the monomer-dimer covering problem in polynomial time. We make two key improvements to their algorithm: we greatly reduce the number of simulations that must be run by estimating good values of the generating function parameter, and we greatly reduce the number of steps that must be taken in each simulation by aggregating to a simulation with at most five states. The result is an algorithm that is computationally feasible for modestly-sized meshes. We use our algorithm on two and three-dimensional problems, computing approximations to the coefficients of the generating function and some limiting values.Citation
Physical Review E (Statistical, Nonlinear, and Soft Matter Physics)
Volume
64
Issue
1
Pub Type
Journals
Download Paper
Keywords
algorithm, dimer covering problem, Monomer-dimer problem, Monte Carlo, Partition function, random walk
Citation
Issues
If you have any questions about this publication or are having problems accessing it, please contact reflib@nist.gov.
Created July 1, 2001, Updated February 17, 2017