کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
5775919 | 1631756 | 2017 | 10 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Computing the k-metric dimension of graphs
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
موضوعات مرتبط
مهندسی و علوم پایه
ریاضیات
ریاضیات کاربردی
پیش نمایش صفحه اول مقاله

چکیده انگلیسی
Given a connected graph G=(V,E), a set S â V is a k-metric generator for G if for any two different vertices u, v â V, there exist at least k vertices w1,â¦,wkâS such that dG(u, wi) â dG(v, wi) for every iâ{1,â¦,k}. A metric generator of minimum cardinality is called a k-metric basis and its cardinality the k-metric dimension of G. We make a study concerning the complexity of some k-metric dimension problems. For instance, we show that the problem of computing the k-metric dimension of graphs is NP-hard. However, the problem is solved in linear time for the particular case of trees.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Applied Mathematics and Computation - Volume 300, 1 May 2017, Pages 60-69
Journal: Applied Mathematics and Computation - Volume 300, 1 May 2017, Pages 60-69
نویسندگان
Ismael G. Yero, Alejandro Estrada-Moreno, Juan A. RodrÃguez-Velázquez,