کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
4662313 | 1633536 | 2008 | 40 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
The parameterized complexity of maximality and minimality problems
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
موضوعات مرتبط
مهندسی و علوم پایه
ریاضیات
منطق ریاضی
پیش نمایش صفحه اول مقاله

چکیده انگلیسی
Many parameterized problems (such as the clique problem and the dominating set problem) ask, given an instance and a natural number k as parameter, whether there is a solution of size k. We analyze the relationship between the complexity of such a problem and the corresponding maximality (minimality) problem asking for a solution of size k maximal (minimal) with respect to set inclusion. As our results show, many maximality problems increase the parameterized complexity, while “in terms of the W-hierarchy” minimality problems do not increase the complexity. We also address the corresponding construction, listing, and counting problems.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Annals of Pure and Applied Logic - Volume 151, Issue 1, January 2008, Pages 22-61
Journal: Annals of Pure and Applied Logic - Volume 151, Issue 1, January 2008, Pages 22-61