کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
431653 688602 2012 9 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Approximation complexity of Metric Dimension problem
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
Approximation complexity of Metric Dimension problem
چکیده انگلیسی

We study the approximation complexity of the Metric Dimension problem   in bounded degree, dense as well as in general graphs. For the general case, we prove that the Metric Dimension problem is not approximable within (1−ϵ)lnn for any ϵ>0ϵ>0, unless NP⊆DTIME(nloglogn)NP⊆DTIME(nloglogn), and we give an approximation algorithm which matches the lower bound.Even for bounded degree instances it is APX-hard to determine (compute) the value of the metric dimension which we prove by constructing an approximation preserving reduction from the bounded degree Vertex Cover problem.The special case, in which the underlying graph is superdense turns out to be APX-complete. In particular, we present a greedy constant factor approximation algorithm for this kind of instances and construct an approximation preserving reduction from the bounded degree Dominating Set problem. We also provide the first explicit approximation lower bounds for the Metric Dimension problem restricted to dense and bounded degree graphs.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Journal of Discrete Algorithms - Volume 14, July 2012, Pages 214–222
نویسندگان
, , ,