کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
6875606 1441975 2018 14 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
T-tetrominoes tiling's Markov chain mixes fast
کلمات کلیدی
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
T-tetrominoes tiling's Markov chain mixes fast
چکیده انگلیسی
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.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Theoretical Computer Science - Volume 714, 1 March 2018, Pages 1-14
نویسندگان
, ,