کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
435855 | 689944 | 2015 | 9 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
On the complexity of the misère version of three games played on graphs
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
چکیده انگلیسی
We investigate the complexity of finding a winning strategy for the misère version of three games played on graphs: two variants of the game NimG, introduced by Stockmann in 2004 and the game Vertex Geography on both directed and undirected graphs. We show that on general graphs those three games are pspace-Hard or Complete. For one pspace-Hard variant of NimG, we find an algorithm to compute an effective winning strategy in time O(|V(G)|.|E(G)|) when G is a bipartite graph.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Theoretical Computer Science - Volume 595, 30 August 2015, Pages 159–167
Journal: Theoretical Computer Science - Volume 595, 30 August 2015, Pages 159–167
نویسندگان
Gabriel Renault, Simon Schmidt,