کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
6875538 | 1441966 | 2018 | 10 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Parameterized algorithms for stable matching with ties and incomplete lists
ترجمه فارسی عنوان
الگوریتم های پارامتریک برای تطابق پایدار با روابط و لیست های ناقص
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
تطبیق پایدار، پیچیدگی پارامتریک، لیست ترجیحی
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
چکیده انگلیسی
We study the parameterized complexity of NP-hard optimization versions of Stable Matching and Stable Roommates in the presence of ties and incomplete lists. These problems model many real-life situations where solutions have to satisfy certain predefined criterion of suitability and compatibility. Specifically, our objective is to maximize/minimize the size of the stable matching. Our main theorems state that Stable Matching and Stable Roommates admit small kernels. Consequently, we also conclude that Stable Matching is fixed-parameter tractable (FPT) with respect to solution size, and that Stable Roommates is FPT with respect to a structural parameter. Finally, we analyze the special case where the input graph is planar.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Theoretical Computer Science - Volume 723, 2 May 2018, Pages 1-10
Journal: Theoretical Computer Science - Volume 723, 2 May 2018, Pages 1-10
نویسندگان
Deeksha Adil, Sushmita Gupta, Sanjukta Roy, Saket Saurabh, Meirav Zehavi,