کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
6875520 | 1441964 | 2018 | 15 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Spy-game on graphs: Complexity and simple topologies
ترجمه فارسی عنوان
بازی جاسوسی بر روی نمودار: پیچیدگی و توپولوژی ساده
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
چکیده انگلیسی
We consider the computational complexity of the problem, showing that it is NP-hard (for every speed s and distance d) and that some variant of it is PSPACE-hard in DAGs. Then, we establish tight tradeoffs between the number of guards, the speed s of the spy and the required distance d when G is a path or a cycle.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Theoretical Computer Science - Volume 725, 16 May 2018, Pages 1-15
Journal: Theoretical Computer Science - Volume 725, 16 May 2018, Pages 1-15
نویسندگان
Nathann Cohen, NÃcolas A. Martins, Fionn Mc Inerney, Nicolas Nisse, Stéphane Pérennes, Rudini Sampaio,