کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
1141411 | 1489495 | 2016 | 11 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Fixed-parameter algorithms for vertex cover P3
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
موضوعات مرتبط
مهندسی و علوم پایه
ریاضیات
کنترل و بهینه سازی
پیش نمایش صفحه اول مقاله
![عکس صفحه اول مقاله: Fixed-parameter algorithms for vertex cover P3 Fixed-parameter algorithms for vertex cover P3](/preview/png/1141411.png)
چکیده انگلیسی
Let Pâ denote a path in a graph G=(V,E) with â vertices. A vertex cover Pâ set C in G is a vertex subset such that every Pâ in G has at least a vertex in C. The Vertex CoverPâ problem is to find a vertex cover Pâ set of minimum cardinality in a given graph. This problem is NP-hard for any integer â⩾2. The parameterized version of Vertex CoverPâ problem called k-Vertex CoverPâ asks whether there exists a vertex cover Pâ set of size at most k in the input graph. In this paper, we give two fixed parameter algorithms to solve the k-Vertex CoverP3 problem. The first algorithm runs in time Oâ(1.7964k) in polynomial space and the second algorithm runs in time Oâ(1.7485k) in exponential space. Both algorithms are faster than previous known fixed-parameter algorithms.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Optimization - Volume 19, February 2016, Pages 12-22
Journal: Discrete Optimization - Volume 19, February 2016, Pages 12-22
نویسندگان
Maw-Shang Chang, Li-Hsuan Chen, Ling-Ju Hung, Peter Rossmanith, Ping-Chen Su,