# Investigation on irreducible cost vectors in minimum cost arborescence problems

*Yoshifumi Kusunoki* and
*Tetsuzo Tanino*

*European Journal of Operational Research*, 2017, vol. 261, issue 1, 214-221

**Abstract:**
We study cost allocation rules in minimum cost arborescence problems, where agents need to build a network to a source in order to obtain some resource. Provided a vector of costs of edges (agent/source pairs), the agents cooperate to construct a minimum cost arborescence rooted at the source in order to reduce the total building cost. Minimum cost arborescence problems are extensions of well-studied minimum cost spanning tree problems to deal with asymmetric edge costs. Regarding cost allocation rules in minimum cost arborescence problems, Dutta and Mishra (2012) extended the folk rule, which is one of the most important rules in minimum cost spanning tree problems, based on the problem with the vector of the most reduced costs, called irreducible form. In minimum cost spanning tree problems, several axiomatic characterizations of the folk rule have been proposed. However, it is difficult to extend them in minimum cost arborescence problems. One of the reasons is that strong and reasonable axioms in minimum cost spanning tree problems, which imply irreducible-form dependence of cost allocation rules, are not satisfied by the folk rule in minimum cost arborescence problems. Hence, we search for other axioms which imply irreducible-form dependence. For this purpose, we investigate irreducible cost vectors in minimum cost arborescence problems, and characterize the irreducible form.

**Keywords:** Game theory; Graph theory; Minimum cost arborescence problem; Irreducible cost; Cost allocation rule (search for similar items in EconPapers)

**Date:** 2017

**References:** View references in EconPapers View complete reference list from CitEc

**Citations** Track citations by RSS feed

**Downloads:** (external link)

http://www.sciencedirect.com/science/article/pii/S0377221717300760

Full text for ScienceDirect subscribers only

**Related works:**

This item may be available elsewhere in EconPapers: Search for items with the same title.

**Export reference:** BibTeX
RIS (EndNote, ProCite, RefMan)
HTML/Text

**Persistent link:** http://EconPapers.repec.org/RePEc:eee:ejores:v:261:y:2017:i:1:p:214-221

Access Statistics for this article

European Journal of Operational Research is currently edited by *Roman Slowinski*, *Jesus Artalejo*, *Jean-Charles. Billaut*, *Robert Dyson* and *Lorenzo Peccati*

More articles in European Journal of Operational Research from Elsevier

Series data maintained by Dana Niculescu ().