کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
4949689 | 1440202 | 2017 | 7 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
On optimal approximability results for computing the strong metric dimension
ترجمه فارسی عنوان
نتایج تقریبی مطلوب برای محاسبه ابعاد متریک قوی است
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
بعد متریک قوی، پوشش حداقل گره، تقریب پذیری، حدس بازی های منحصر به فرد، فرضیه زمانی معین، پیچیدگی پارامتریک،
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
چکیده انگلیسی
The strong metric dimension of a graph was first introduced by Sebö and Tannier (2004) as an alternative to the (weak) metric dimension of graphs previously introduced independently by Slater (1975) and by Harary and Melter (1976), and has since been investigated in several research papers. However, the exact worst-case computational complexity of computing the strong metric dimension has remained open beyond being NP-complete. In this communication, we show that the problem of computing the strong metric dimension of a graph of n nodes admits a polynomial-time 2-approximation, admits a Oâ(20.287n)-time exact computation algorithm, admits a O(1.2738k+nk)-time exact computation algorithm if the strong metric dimension is at most k, does not admit a polynomial time (2âε)-approximation algorithm assuming the unique games conjecture is true, does not admit a polynomial time (105â21âε)-approximation algorithm assuming Pâ NP, does not admit a Oâ(2o(n))-time exact computation algorithm assuming the exponential time hypothesis is true, and does not admit a Oâ(no(k))-time exact computation algorithm if the strong metric dimension is at most k assuming the exponential time hypothesis is true.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Applied Mathematics - Volume 221, 20 April 2017, Pages 18-24
Journal: Discrete Applied Mathematics - Volume 221, 20 April 2017, Pages 18-24
نویسندگان
Bhaskar DasGupta, Nasim Mobasheri,