Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
6875606 | Theoretical Computer Science | 2018 | 14 Pages |
Abstract
Korn and Pak (2007) [3] conjectured that there exists a fully polynomial randomized approximation scheme (fpras) for approximating the number of ways of tiling a 4nÃ4m rectangular lattice with T-tetrominoes. Using a flow argument, we prove this conjecture in affirmative by showing that the mixing time of an appropriate Markov chain is polynomial in the area of the lattice.
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
K.K. Kayibi, S. Pirzada,