All Rights Reserved
AccessEcon LLC 2006, 2008.
Powered by MinhViet JSC

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

  This abstract has been downloaded 1400 times                The Full PDF of this paper has been downloaded 153839 times