کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
4952190 | 1442019 | 2017 | 11 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Hardness results for stable exchange problems
ترجمه فارسی عنوان
سختی نتایج مسائل با ثبات است
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
تبادل پایدار، تبادل کلیه، پیچیدگی محاسباتی، پارتیشن پایدار
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
چکیده انگلیسی
In this paper, we study variants of the stable exchange problem which can be viewed as a model for kidney exchange. The b-way stable l-way exchange problem is a generalization of the stable roommates problem. For b=l=3, Biró and McDermid (2010) [1] proved that the problem is NP-complete and asked whether a polynomial time algorithm exists for b=2, l=3. We prove that the problem is NP-complete and it is W[1]-hard with the number of 3-cycles in the exchange as a parameter. We answer a question of Biró (2007) [2] by proving that it is NP-hard to maximize the number of covered nodes in a stable exchange. We also prove some related results on strong stability and approximation.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Theoretical Computer Science - Volume 670, 29 March 2017, Pages 68-78
Journal: Theoretical Computer Science - Volume 670, 29 March 2017, Pages 68-78
نویسندگان
Zsuzsa Mészáros-Karkus,