کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
5775919 1631756 2017 10 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Computing the k-metric dimension of graphs
موضوعات مرتبط
مهندسی و علوم پایه ریاضیات ریاضیات کاربردی
پیش نمایش صفحه اول مقاله
Computing the k-metric dimension of graphs
چکیده انگلیسی
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
نویسندگان
, , ,