کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
10225757 | 1701211 | 2018 | 24 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Contraction and deletion blockers for perfect graphs and H-free graphs
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
چکیده انگلیسی
We study the following problem: for given integers d, k and graph G, can we reduce some fixed graph parameter Ï of G by at least d via at most k graph operations from some fixed set S? As parameters we take the chromatic number Ï, clique number Ï and independence number α, and as operations we choose edge contraction ec and vertex deletion vd. We determine the complexity of this problem for S={ec} and S={vd} and Ïâ{Ï,Ï,α} for a number of subclasses of perfect graphs. We use these results to determine the complexity of the problem for S={ec} and S={vd} and Ïâ{Ï,Ï,α} restricted to H-free graphs.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Theoretical Computer Science - Volume 746, 25 October 2018, Pages 49-72
Journal: Theoretical Computer Science - Volume 746, 25 October 2018, Pages 49-72
نویسندگان
Ãznur YaÅar Diner, Daniël Paulusma, Christophe Picouleau, Bernard Ries,