Cover Image

A note on maximizing the minimum voter satisfaction on spanning trees

A fair spanning tree of a graph maximizes the minimum satisfaction among individuals given their preferences over the edges of the graph. In this note we answer an open question about the computational complexity of determining fair spanning trees raised in Darmann et al. (2009). It is shown that the maximin voter satisfaction problem under choose-t elections is -complete for each fixed t>=2.
Year of publication:
2010
Authors: Darmann, Andreas ; Klamler, Christian ; Pferschy, Ulrich
Published in:
Mathematical Social Sciences. - Elsevier, ISSN 0165-4896. - Vol. 60.2010, 1, p. 82-85
Publisher: Elsevier
Keywords: Minimal spanning tree Social choice Fairness
Type of publication: Article
Source:
Persistent link: https://www.econbiz.de/10008488322
Similar items by person