Article ID Journal Published Year Pages File Type
972303 Mathematical Social Sciences 2009 13 Pages PDF
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
, , ,