### Abstract

Original language | English |
---|---|

Pages (from-to) | 440-453 |

Journal | Top |

Volume | 17 |

Issue number | 2 |

Publication status | Published - 2009 |

### Fingerprint

### Cite this

*Top*,

*17*(2), 440-453.

}

*Top*, vol. 17, no. 2, pp. 440-453.

**A vertex oriented approach to the equal remaining obligations rule for the minimum cost spanning tree problems.** / Ciftci, B.B.; Tijs, S.H.

Research output: Contribution to journal › Article › Scientific › peer-review

TY - JOUR

T1 - A vertex oriented approach to the equal remaining obligations rule for the minimum cost spanning tree problems

AU - Ciftci, B.B.

AU - Tijs, S.H.

N1 - Appeared earlier as CentER DP 2007-89

PY - 2009

Y1 - 2009

N2 - In this paper, we consider spanning tree situations, where players want to be connected to a source as cheap as possible. These situations involve the construction of a spanning tree with the minimum cost as well as the allocation of the cost of this minimum cost spanning tree among its users in a fair way. Feltkamp, Muto and Tijs 1994 introduced the equal remaining obligations rule to solve the cost allocation problem in these situations. Recently, it has been shown that the equal remaining obligations rule satisfies many appealing properties and can be obtained with different approaches. In this paper, we provide a new approach to obtain the equal remaining obligations rule. Specifically, we show that the equal remaining obligations rule can be obtained as the average of the cost allocations provided by a vertex oriented construct-and-charge procedure for each order of players.

AB - In this paper, we consider spanning tree situations, where players want to be connected to a source as cheap as possible. These situations involve the construction of a spanning tree with the minimum cost as well as the allocation of the cost of this minimum cost spanning tree among its users in a fair way. Feltkamp, Muto and Tijs 1994 introduced the equal remaining obligations rule to solve the cost allocation problem in these situations. Recently, it has been shown that the equal remaining obligations rule satisfies many appealing properties and can be obtained with different approaches. In this paper, we provide a new approach to obtain the equal remaining obligations rule. Specifically, we show that the equal remaining obligations rule can be obtained as the average of the cost allocations provided by a vertex oriented construct-and-charge procedure for each order of players.

M3 - Article

VL - 17

SP - 440

EP - 453

JO - Top

JF - Top

SN - 1134-5764

IS - 2

ER -