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

B.B. Ciftci, S.H. Tijs

Research output: Contribution to journalArticleScientificpeer-review

Abstract

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.
Original languageEnglish
Pages (from-to)440-453
JournalTop
Volume17
Issue number2
Publication statusPublished - 2009

Fingerprint

Spanning tree
Cost Allocation
Costs
Vertex of a graph
Charge

Cite this

@article{e2eeaf2c0a1a4af58d2f7b2f84aa4159,
title = "A vertex oriented approach to the equal remaining obligations rule for the minimum cost spanning tree problems",
abstract = "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.",
author = "B.B. Ciftci and S.H. Tijs",
note = "Appeared earlier as CentER DP 2007-89",
year = "2009",
language = "English",
volume = "17",
pages = "440--453",
journal = "Top",
issn = "1134-5764",
publisher = "Springer Verlag",
number = "2",

}

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 journalArticleScientificpeer-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 -