科研之友
微信
新浪微博
Facebook
分享链接
摘要
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 NP-complete for each fixed t >= 2.
- 出版日期2010-7
