کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
427105 686448 2015 6 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Computing the metric dimension for chain graphs
ترجمه فارسی عنوان
محاسبه ابعاد متریک برای نمودارهای زنجیره ای
کلمات کلیدی
مشکلات ترکیبی بعد متریک، بعد متریک مجاورت، نمودارهای زنجیره ای، الگوریتم های چندجملهای زمان
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر نظریه محاسباتی و ریاضیات
چکیده انگلیسی


• We show how to compute the metric dimension of bipartite chain graphs.
• Our algorithm works in linear time even on compact representations.
• We also conclude combinatorial results for simple chain graphs.
• Our order-theoretic arguments may be useful for other problems, as well.
• We indicate this for some variants of metric dimension.

The metric dimension of a graph G is the smallest size of a set R of vertices that can distinguish each vertex pair of G by the shortest-path distance to some vertex in R. Computing the metric dimension is NP-hard, even when restricting inputs to bipartite graphs. We present a linear-time algorithm for computing the metric dimension for chain graphs, which are bipartite graphs whose vertices can be ordered by neighborhood inclusion.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Information Processing Letters - Volume 115, Issue 9, September 2015, Pages 671–676
نویسندگان
, , , , ,