کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
4630963 | 1340612 | 2011 | 8 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Minesweeper on graphs
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
موضوعات مرتبط
مهندسی و علوم پایه
ریاضیات
ریاضیات کاربردی
پیش نمایش صفحه اول مقاله

چکیده انگلیسی
Minesweeper is a popular single player game. It has been shown that the Minesweeper consistency problem is NP-complete and the Minesweeper counting problem is #P-complete. In this paper, we present efficient algorithms for solving these problems for Minesweeper graphs with bounded treewidth. Our algorithms turn out to be much better than those based directly on dynamic programming. The algorithms mostly use of algebraic operations on multivariate polynomials, so that one may use existing software to implement them easily.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Applied Mathematics and Computation - Volume 217, Issue 14, 15 March 2011, Pages 6616–6623
Journal: Applied Mathematics and Computation - Volume 217, Issue 14, 15 March 2011, Pages 6616–6623
نویسندگان
Shahar Golan,