کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
6871590 | 1440187 | 2018 | 13 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Tree spanners of bounded degree graphs
ترجمه فارسی عنوان
کلید های درختی نمودارهای درجه محدود
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
دنده درخت فاصله، درخت پوشا، الگوریتم گراف کارآمد، نمودار درجه محدود
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
چکیده انگلیسی
A tree t-spanner of a graph G is a spanning tree of G such that the distance between pairs of vertices in the tree is at most t times their distance in G. Deciding tree t-spanner admissible graphs has been proved to be tractable for t<3 and NP-complete for t>3, while the complexity status of this problem is unresolved when t=3. For every t>2 and b>0, an efficient dynamic programming algorithm to decide tree t-spanner admissibility of graphs with vertex degrees less than b is presented. Only for t=3, the algorithm remains efficient, when graphs G with degrees less than blog|V(G)| are examined.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Applied Mathematics - Volume 236, 19 February 2018, Pages 395-407
Journal: Discrete Applied Mathematics - Volume 236, 19 February 2018, Pages 395-407
نویسندگان
Ioannis Papoutsakis,