کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
972303 | 932552 | 2009 | 13 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Maximizing the minimum voter satisfaction on spanning trees
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
موضوعات مرتبط
مهندسی و علوم پایه
ریاضیات
ریاضیات کاربردی
پیش نمایش صفحه اول مقاله
چکیده انگلیسی
This paper analyzes the computational complexity involved in solving fairness issues on graphs, e.g., in the installation of networks such as water networks or oil pipelines. Based on individual rankings of the edges of a graph, we will show under which conditions solutions, i.e., spanning trees, can be determined efficiently given the goal of maximin voter satisfaction. In particular, we show that computing spanning trees for maximin voter satisfaction under voting rules such as approval voting or the Borda count is NP-complete for a variable number of voters whereas it remains polynomially solvable for a constant number of voters.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Mathematical Social Sciences - Volume 58, Issue 2, September 2009, Pages 238-250
Journal: Mathematical Social Sciences - Volume 58, Issue 2, September 2009, Pages 238-250
نویسندگان
Andreas Darmann, Christian Klamler, Ulrich Pferschy,