کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
6875580 | 1441972 | 2018 | 11 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Parameterized complexity of team formation in social networks
ترجمه فارسی عنوان
پیچیدگی پارامترهای تشکیل تیم در شبکه های اجتماعی
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
تجزیه و تحلیل پیچیدگی محاسباتی، تجزیه و تحلیل پیچیدگی پارامتریک، تشکیل تیم در شبکه های اجتماعی،
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
چکیده انگلیسی
Given a task that requires some skills and a social network of individuals with different skills, the Team Formation problem asks to find a team of individuals that together can perform the task, while minimizing communication costs. Since the problem is NP-hard, we identify the source of intractability by analyzing its parameterized complexity with respect to parameters such as the total number of skills k, the team size l, the communication cost budget b, and the maximum vertex degree Î. We show that the computational complexity strongly depends on the communication cost measure: when using the weight of a minimum spanning tree of the subgraph formed by the selected team, we obtain fixed-parameter tractability for example with respect to the parameter k. In contrast, when using the diameter as measure, the problem is intractable with respect to any single parameter; however, combining Î with either b or l yields fixed-parameter tractability.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Theoretical Computer Science - Volume 717, 22 March 2018, Pages 26-36
Journal: Theoretical Computer Science - Volume 717, 22 March 2018, Pages 26-36
نویسندگان
Robert Bredereck, Jiehua Chen, Falk Hüffner, Stefan Kratsch,