|
|
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 |
|