It is hard to agree on a spanning tree

Andreas Darmann ()
Additional contact information
Andreas Darmann: Institute of Public Economics, University of Graz

Economics Bulletin, 2014, vol. 34, issue 1, 34-40

Abstract: 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 (search for similar items in EconPapers)
JEL-codes: D7 (search for similar items in EconPapers)
Date: 2014-01-14
References: Add references at CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
http://www.accessecon.com/Pubs/EB/2014/Volume34/EB-14-V34-I1-P4.pdf (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:ebl:ecbull:eb-13-00831

Access Statistics for this article

More articles in Economics Bulletin from AccessEcon
Bibliographic data for series maintained by John P. Conley ().