کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
6874177 | 1441027 | 2018 | 6 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
On the hardness of finding the geodetic number of a subcubic graph
ترجمه فارسی عنوان
در سختی پیدا کردن تعداد ژئودزی از یک نمودار زیرکوبیک
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
شماره ژئودتیک، مجموعه ژئودتیک، محدب جغرافیایی، پیچیدگی محاسباتی، حداکثر درجه سه
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
چکیده انگلیسی
A set of vertices D of a graph G is geodetic if every vertex of G lies in a shortest path between two vertices in D. The geodetic number of G is the minimum cardinality of a geodetic set of G, and deciding whether it is at most k is an NP-complete problem for several classes of graphs. While the problem is easy for graphs of maximum degree at most 2, we show that the problem is NP-complete for graphs of maximum degree three.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Information Processing Letters - Volume 135, July 2018, Pages 22-27
Journal: Information Processing Letters - Volume 135, July 2018, Pages 22-27
نویسندگان
LetÃcia R. Bueno, Lucia D. Penso, Fábio Protti, Victor R. Ramos, Dieter Rautenbach, Uéverton S. Souza,