کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
10225756 | 1701211 | 2018 | 13 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
On the (parameterized) complexity of recognizing well-covered (r,â)-graph
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
چکیده انگلیسی
An (r,â)-partition of a graph G is a partition of its vertex set into r independent sets and â cliques. A graph is (r,â) if it admits an (r,â)-partition. A graph is well-covered if every maximal independent set is also maximum. A graph is (r,â)-well-covered if it is both (r,â) and well-covered. In this paper we consider two different decision problems. In the (r,â)-Well-Covered Graph problem ((r,â)wc-g for short), we are given a graph G, and the question is whether G is an (r,â)-well-covered graph. In the Well-Covered(r,â)-Graph problem (wc-(r,â)g for short), we are given an (r,â)-graph G together with an (r,â)-partition, and the question is whether G is well-covered. This generates two infinite families of problems, for any fixed non-negative integers r and â, which we classify as being P, coNP-complete, NP-complete, NP-hard, or coNP-hard. Only the cases wc-(r,0)g for râ¥3 remain open. In addition, we consider the parameterized complexity of these problems for several choices of parameters, such as the size α of a maximum independent set of the input graph, its neighborhood diversity, its clique-width, or the number â of cliques in an (r,â)-partition. In particular, we show that the parameterized problem of determining whether every maximal independent set of an input graph G has cardinality equal to k can be reduced to the wc-(0,â)g problem parameterized by â. In addition, we prove that both problems are coW[2]-hard but can be solved in XP-time.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Theoretical Computer Science - Volume 746, 25 October 2018, Pages 36-48
Journal: Theoretical Computer Science - Volume 746, 25 October 2018, Pages 36-48
نویسندگان
Sancrey Rodrigues Alves, Konrad K. Dabrowski, Luerbio Faria, Sulamita Klein, Ignasi Sau, Uéverton S. Souza,