کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
9655123 | 684030 | 2005 | 17 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Fast fixed-parameter tractable algorithms for nontrivial generalizations of vertex cover
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
چکیده انگلیسی
Our results are obtained by considering bounded-degree minor-closed classes for which all obstructions are connected graphs, and showing that the size of any obstruction for Wk(G) is O(tk7+t7k2), where t is a bound on the size of obstructions for G. A trivial corollary of this result is an upper bound of (k+1)(k+2) on the number of vertices in any obstruction of the class of graphs with vertex cover of size at most k. These results are of independent graph-theoretic interest.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Applied Mathematics - Volume 152, Issues 1â3, 1 November 2005, Pages 229-245
Journal: Discrete Applied Mathematics - Volume 152, Issues 1â3, 1 November 2005, Pages 229-245
نویسندگان
Naomi Nishimura, Prabhakar Ragde, Dimitrios M. Thilikos,