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

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