Seminar On Minimum cost spanning tree problems and extensions

María Gómez-Rúa (Universidad de Vigo)

Seminar on Minimum cost spanning tree problems and extensions.

January 15th 2015

Class: E-03 at 16:30

ABSTRACT: Mínimum cost spanning tree problems are used to model situations where a group of agents, located at different geographical points, want a particular service which is provided by a common supplier, or source. The agents will be served through connections which entail some cost. However, agents do not care whether they are connected directly or indirectly to the source. Many economic situations can be modeled in this way, for instance, some houses in a village may want to be connected to a common water source or to a power plant. Other examples include communication networks such as Internet, cable television or telephone. 

In order to study these situations, two steps should be considered: in the first one, agents will construct a minimal cost spanning tree, and once this tree is constructed, the second step consists on dividing its cost between the nodes that benefit from it. In order to do that a rule is used.

Different rules are usually associated with alternative sets of desired axioms. The aim of the axiomatic characterization is to identify a well-defined set of properties for each rule. 

Apart from the classical model, there exist many other extensions that modelize different real life situations.