Abstract
Original language | English |
---|---|
Pages (from-to) | 440-453 |
Journal | Top |
Volume | 17 |
Issue number | 2 |
Publication status | Published - 2009 |
Fingerprint
Cite this
}
A vertex oriented approach to the equal remaining obligations rule for the minimum cost spanning tree problems. / Ciftci, B.B.; Tijs, S.H.
In: Top, Vol. 17, No. 2, 2009, p. 440-453.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 -