It is hard to agree on a spanning tree

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.

MoreLess

Year of publication:	2014-01-14
Authors:	Darmann, Andreas
Published in:	Economics Bulletin. - AccessEcon, ISSN 1545-2921. - Vol. 34.2014, 1, p. 34-40
Publisher:	AccessEcon
Subject:	social choice \| spanning trees \| computational complexity

More details

Extent:	application/pdf
Type of publication:	Article
Classification:	D7 - Analysis of Collective Decision-Making
Source:	RePEc - Research Papers in Economics

Persistent link: https://ebvufind01.dmz1.zbw.eu/10010734309