Show simple item record

AuthorKayibi K.K.
AuthorPirzada S.
Available date2020-01-01T10:25:02Z
Publication Date2018
Publication NameTheoretical Computer Science
ResourceScopus
ISSN0304-3975
URIhttp://dx.doi.org/10.1016/j.tcs.2017.12.020
URIhttp://hdl.handle.net/10576/12434
AbstractKorn 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 x 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. - 2017 Elsevier B.V.
SponsorThe authors thank the anonymous referees for their valuable comments and suggestions. We would like to thank Qatar University, Doha, Qatar, and University of Hull, UK, and University of Kashmir, Srinagar, India for providing facilities and support during the preparation of the final form of this paper. The research of second author is supported by SERB-DST , New Delhi under the research project number EMR/2015/001047/MS .
Languageen
PublisherElsevier B.V.
SubjectFpras
Mixing time of Markov chains
T-tetromino
Tiling
TitleT-tetrominoes tiling's Markov chain mixes fast
TypeArticle
PaginationJan-14
Volume Number714
dc.accessType Abstract Only


Files in this item

FilesSizeFormatView

There are no files associated with this item.

This item appears in the following Collection(s)

Show simple item record