On the irreducible core and the equal remaining obligations rule of minimum cost spanning extension problems

TLDR

Minimum cost spanning extension problems generalize minimum cost spanning tree problems by extending an existing network to connect users to a source. The paper extends the concept of irreducible core to these problems and proposes an algorithm to enumerate all irreducible core elements. It also introduces the equal remaining obligations rule, a refinement of the irreducible core, within the algorithmic framework. The solutions are axiomatized, and the classical Bird tree allocation emerges as a special case of the algorithm.

Abstract

Minimum cost spanning extension problems are generalizations of minimum cost spanning tree problems in which an existing network has to be extended to connect users to a source. This paper generalizes the definition of irreducible core to minimum cost spanning extension problems and introduces an algorithm generating all elements of the irreducible core. Moreover, the equal remaining obligations rule, a one-point refinement of the irreducible core ispresented. Finally, the paper characterizes these solutions axiomatically. The classical Bird tree allocation of minimum cost spanning tree problems is obtained as a particular case in our algorithm for the irreducible core.