A new rule for source connection problems
- G. Bergantiños 1
- M. Gómez-Rúa 1
- N. Llorca 2
- M. Pulido 3
- J. Sánchez-Soriano 2
-
1
Universidade de Vigo
info
-
2
Universidad Miguel Hernández de Elche
info
-
3
Universidad de Murcia
info
Year of publication: 2012
Issue: 1
Type: Working paper
Abstract
In this paper we study situations where a group of agents need a service that could be only provided by a source. We call it source connection problems. This class of problems contain the standard xed tree problems, the classical minimum spanning tree problems and some other related problems like the k hop, the degree constrained and the generalized minimum spanning tree among others. Our goal is to divide the cost of the tree among the agents. We introduce a rule, called painting rule because it can be interpreted through a story about painting. We present some meaningful properties in this context and provide a characterization of the rule.