Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
972303 | Mathematical Social Sciences | 2009 | 13 Pages |
Abstract
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.
Related Topics
Physical Sciences and Engineering
Mathematics
Applied Mathematics
Authors
Andreas Darmann, Christian Klamler, Ulrich Pferschy,