T-tetrominoes tiling's Markov chain mixes fast
Review articleOpen access
K.K. Kayibi - No affiliation found
2018/03/01 Full-length article DOI: 10.1016/j.tcs.2017.12.020
Journal: Theoretical Computer Science
AbstractKorn and Pak (2007)  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.
Request full text