A network flow approach to cost allocation for rooted trees

A network flow approach to cost allocation for rooted trees

0.00 Avg rating0 Votes
Article ID: iaor20051022
Country: Netherlands
Volume: 44
Issue: 4
Start Page Number: 297
End Page Number: 301
Publication Date: Sep 2004
Journal: Networks
Authors: ,
Keywords: networks: flow
Abstract:

In the game theory approach to cost allocation, the main computational issue is an algorithm for finding solutions such as the Shapley value and the nucleolus. In this article, we consider the problem of allocating the maintenance cost of a tree network that connects the supply source at the root to the users at the leaves. We show that the core of the game can be expressed in terms of network flows. Based on this observation, we present O(n log n) algorithms for computing the nucleolus and the egalitarian allocation.

Reviews

Required fields are marked *. Your email address will not be published.