کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
4951215 | 1441194 | 2017 | 18 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
The control complexity of r-Approval: From the single-peaked case to the general case
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله

چکیده انگلیسی
We investigate the complexity of r-Approval control problems in k-peaked elections, where at most k peaks are allowed in each vote with respect to an order of the candidates. Our study leads to many dichotomy results with respect to the values of k and r. All our NP-completeness results apply to Approval and sincere-strategy preference-based Approval as well. In addition, we study r-Approval control problems from the viewpoint of parameterized complexity and achieve both fixed-parameter tractability results and W[1]-hardness results, with respect to the solution size. Along the way exploring the control problems, we obtain two byproducts which are of independent interest. First, we prove that every graph of maximum degree 3 admits a specific 2-interval representation. Second, we develop a fixed-parameter tractable algorithm for a generalized r-Set Packing problem.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Journal of Computer and System Sciences - Volume 89, November 2017, Pages 432-449
Journal: Journal of Computer and System Sciences - Volume 89, November 2017, Pages 432-449
نویسندگان
Yongjie Yang, Jiong Guo,