๐”– Bobbio Scriptorium
โœฆ   LIBER   โœฆ

A note on maximizing the minimum voter satisfaction on spanning trees

โœ Scribed by Andreas Darmann; Christian Klamler; Ulrich Pferschy

Publisher
Elsevier Science
Year
2010
Tongue
English
Weight
286 KB
Volume
60
Category
Article
ISSN
0165-4896

No coin nor oath required. For personal study only.

๐Ÿ“œ SIMILAR VOLUMES

Maximizing the minimum voter satisfactio
Maximizing the minimum voter satisfaction on spanning trees
โœ Andreas Darmann; Christian Klamler; Ulrich Pferschy ๐Ÿ“‚ Article ๐Ÿ“… 2009 ๐Ÿ› Elsevier Science ๐ŸŒ English โš– 689 KB

This paper analyzes the computational complexity involved in solving fairness issues on graphs, e.g., in the installation of networks such as water networks or oil pipelines. Based on individual rankings of the edges of a graph, we will show under which conditions solutions, i.e., spanning trees, ca

A note on bisecting minimum spanning tre
A note on bisecting minimum spanning trees
โœ W. M. Boyce; M. R. Garey; D. S. Johnson ๐Ÿ“‚ Article ๐Ÿ“… 1978 ๐Ÿ› John Wiley and Sons ๐ŸŒ English โš– 281 KB
A note on the minimum label spanning tre
A note on the minimum label spanning tree
โœ Yingyu Wan; Guoliang Chen; Yinlong Xu ๐Ÿ“‚ Article ๐Ÿ“… 2002 ๐Ÿ› Elsevier Science ๐ŸŒ English โš– 44 KB

We give a tight analysis of the greedy algorithm introduced by Krumke and Wirth for the minimum label spanning tree problem. The algorithm is shown to be a (ln(n -1) + 1)-approximation for any graph with n nodes (n > 1), which improves the known performance guarantee 2 ln n + 1.