کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
420267 | 683915 | 2010 | 13 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Polynomial kernels for 3-leaf power graph modification problems
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
![عکس صفحه اول مقاله: Polynomial kernels for 3-leaf power graph modification problems Polynomial kernels for 3-leaf power graph modification problems](/preview/png/420267.png)
چکیده انگلیسی
A graph G=(V,E)G=(V,E) is a 3-leaf power iff there exists a tree TT the leaf set of which is VV and such that uv∈Euv∈E iff uu and vv are at distance at most 3 in TT. The 3-leaf power graph edge modification problems, i.e. edition (also known as the closest 3-leaf power), completion and edge-deletion are FPT when parameterized by the size of the edge set modification. However, polynomial kernels were known for none of these three problems. For each of them, we provide kernels with O(k3)O(k3) vertices that can be computed in linear time. We thereby answer an open problem first mentioned by Dom et al. (2004) [8].
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Applied Mathematics - Volume 158, Issue 16, 28 August 2010, Pages 1732–1744
Journal: Discrete Applied Mathematics - Volume 158, Issue 16, 28 August 2010, Pages 1732–1744
نویسندگان
Stéphane Bessy, Christophe Paul, Anthony Perez,