Finding socially best spanning trees |
| |
Authors: | Andreas Darmann Christian Klamler Ulrich Pferschy |
| |
Institution: | 1.Institute of Public Economics,University of Graz,Graz,Austria;2.Institute of Statistics and Operations Research,University of Graz,Graz,Austria |
| |
Abstract: | This article combines Social Choice Theory with Discrete Optimization. We assume that individuals have preferences over edges
of a graph that need to be aggregated. The goal is to find a socially “best” spanning tree in the graph. As ranking all spanning
trees is becoming infeasible even for small numbers of vertices and/or edges of a graph, our interest lies in finding algorithms
that determine a socially “best” spanning tree in a simple manner. This problem is closely related to the minimum (or maximum)
spanning tree problem in Discrete Optimization. Our main result shows that for the various underlying ranking rules on the
set of spanning trees discussed in this article, the sets of “best” spanning trees coincide. Moreover, a greedy algorithm
based on a transitive group ranking on the set of edges will always provide such a “best” spanning tree. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|