|
| |
| Andreas Darmann |
| |
| ''It is hard to agree on a spanning tree'' |
| ( 2014, Vol. 34 No.1 ) |
| |
| |
| We consider the problem of finding a "fair" or "acceptable" spanning tree in an undirected graph when each member of a group of agents proposes a spanning tree. An "acceptable" spanning tree in that respect is a spanning tree which does not differ in more than a given number of edges from each of the single proposals. We show that, from a computational perspective, determining if such a spanning tree exists is a difficult (NP-complete) problem. |
| |
| |
| Keywords: social choice, spanning trees, computational complexity |
JEL: D7 - Analysis of Collective Decision-Making: General
|
| |
| Manuscript Received : Dec 17 2013 | | Manuscript Accepted : Jan 14 2014 |
|
