کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
435366 | 689899 | 2016 | 12 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
More results on the complexity of identifying problems in graphs
ترجمه فارسی عنوان
نتایج بیشتر در مورد پیچیدگی شناسایی مشکلات در نمودارها
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
چکیده انگلیسی
We investigate the complexity of several problems linked with identification in graphs; for instance, given an integer r≥1r≥1 and a graph G=(V,E)G=(V,E), the existence of, or search for, optimal r-identifying codes in G, or optimal r-identifying codes in G containing a subset of vertices X⊂VX⊂V. We locate these problems in the complexity classes of the polynomial hierarchy.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Theoretical Computer Science - Volume 626, 2 May 2016, Pages 1–12
Journal: Theoretical Computer Science - Volume 626, 2 May 2016, Pages 1–12
نویسندگان
Olivier Hudry, Antoine Lobstein,