کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
435241 | 689884 | 2016 | 20 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
A linear time algorithm for metric dimension of cactus block graphs
ترجمه فارسی عنوان
الگوریتم زمان خطی برای ابعاد متریک بلوک های کاکتوس
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
الگوریتم زمان خطی، بعد متریک، نمودار بلوک کاکتوس، تنظیم حل
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
چکیده انگلیسی
An undirected graph G=(V,E)G=(V,E) has metric dimension at most k if there is a vertex set U⊆VU⊆V such that |U|≤k|U|≤k and ∀u,v∈V∀u,v∈V, u≠vu≠v, there is a vertex w∈Uw∈U such that dG(w,u)≠dG(w,v)dG(w,u)≠dG(w,v), where dG(u,v)dG(u,v) is the distance (the length of a shortest path in an unweighted graph) between u and v. The metric dimension of G is the smallest integer k such that G has metric dimension at most k. A cactus block graph is an undirected graph whose biconnected components are either cycles or complete graphs. We present a linear time algorithm for computing the metric dimension of cactus block graphs.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Theoretical Computer Science - Volume 630, 30 May 2016, Pages 43–62
Journal: Theoretical Computer Science - Volume 630, 30 May 2016, Pages 43–62
نویسندگان
Stefan Hoffmann, Alina Elterman, Egon Wanke,