کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
419693 | 683850 | 2013 | 6 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
The parametric complexity of graph diameter augmentation
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
![عکس صفحه اول مقاله: The parametric complexity of graph diameter augmentation The parametric complexity of graph diameter augmentation](/preview/png/419693.png)
چکیده انگلیسی
The diameter of a graph is the maximum distance between any pair of vertices in the graph. The Diameter-ttAugmentation problem takes as input a graph G=(V,E)G=(V,E) and a positive integer kk and asks whether there exists a set E2E2 of at most kk new edges so that the graph G2=(V,E∪E2)G2=(V,E∪E2) has diameter tt. This problem is NP-hard (Schoone et al. 1987) [10], even in the t=2t=2 case (Li et al. 1992) [7]. We give a parameterized reduction from Dominating Set to Diameter-ttAugmentation to prove that Diameter-ttAugmentation is W[2]W[2]-hard for every tt.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Applied Mathematics - Volume 161, Issues 10–11, July 2013, Pages 1626–1631
Journal: Discrete Applied Mathematics - Volume 161, Issues 10–11, July 2013, Pages 1626–1631
نویسندگان
Yong Gao, Donovan R. Hare, James Nastos,