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

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.

Cite this work

No public copy is stored for this record, so only the metadata is cited.

Stored only when both papers are in the corpus — 62 citations exist upstream.