کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
10331866 | 686963 | 2015 | 4 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
A fixed-parameter algorithm for the vertex cover P3 problem
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
![عکس صفحه اول مقاله: A fixed-parameter algorithm for the vertex cover P3 problem A fixed-parameter algorithm for the vertex cover P3 problem](/preview/png/10331866.png)
چکیده انگلیسی
A subset F of vertices of a graph G is called a vertex cover Pt set if every path of order t in G contains at least one vertex from F. Denote by Ït(G) the minimum cardinality of a vertex cover Pt set in G. The vertex cover Pt (VCPt) problem is to find a minimum vertex cover Pt set. The VCPt problem is NP-hard for any integer tâ¥2. In this paper, we restrict our attention to the VCP3 problem and present a fixed-parameter algorithm with runtime O(2kk3.376+n4m) for the VCP3 problem. Here, n denotes the number of vertices, m denotes the number of the edges, k denotes the size of the vertex cover P3 set searched for.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Information Processing Letters - Volume 115, Issue 2, February 2015, Pages 96-99
Journal: Information Processing Letters - Volume 115, Issue 2, February 2015, Pages 96-99
نویسندگان
Jianhua Tu,