کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
4951283 | 1364339 | 2017 | 27 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Complexity of metric dimension on planar graphs
ترجمه فارسی عنوان
پیچیدگی ابعاد متریک بر روی نمودارهای مسطح
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
چکیده انگلیسی
The metric dimension of a graph G is the size of a smallest subset LâV(G) such that for any x,yâV(G) with xâ y there is a zâL such that the graph distance between x and z differs from the graph distance between y and z. Even though this notion has been part of the literature for almost 40 years, prior to our work the computational complexity of determining the metric dimension of a graph was still very unclear. In this paper, we show tight complexity boundaries for the Metric Dimension problem. We achieve this by giving two complementary results. First, we show that the Metric Dimension problem on planar graphs of maximum degree 6 is NP-complete. Then, we give a polynomial-time algorithm for determining the metric dimension of outerplanar graphs.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Journal of Computer and System Sciences - Volume 83, Issue 1, February 2017, Pages 132-158
Journal: Journal of Computer and System Sciences - Volume 83, Issue 1, February 2017, Pages 132-158
نویسندگان
Josep Diaz, Olli Pottonen, Maria Serna, Erik Jan van Leeuwen,