Demand Operators and the Dutta-Kar Rule for Minimum Cost Spanning Tree Problems

Youngsub Chun, Chang-Yong Han and Bawoo Kim

Working Paper Series from Institute of Economic Research, Seoul National University

Abstract: We investigate the implications of two demand operators, the weak demand operator and the strong demand operator, introduced by Granot and Huberman (1984) for minimum cost spanning tree problems (mcstp¡¯s). The demand operator is intended to measure the maximum amount that each agent can ask to her followers in compensation for making a link to her. However, the original definition of the weak demand operator does not capture this idea and we propose its modification. Then, we introduce a procedure which enables us to calculate the maximum sequentially for each agent. By applying the modified weak demand operator to the irreducible mcstp¡¯s, the Dutta-Kar allocation is obtained from any component-wise efficient initial allocation. For the strong demand operator, the Dutta-Kar allocation can be obtained if the procedure is initiated from any allocation in the irreducible core.

Keywords: Minimum cost spanning tree problems; demand operators, irreducible matrix; Dutta-Kar rule; Prim algorithm (search for similar items in EconPapers)
JEL-codes: C71 (search for similar items in EconPapers)
Date: 2013-03
References: Add references at CitEc
Citations:

Downloads: (external link)
https://ier.snu.ac.kr/activity/working-papers?md=download&seqidx=37

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: https://EconPapers.repec.org/RePEc:snu:ioerwp:no88

Access Statistics for this paper

More papers in Working Paper Series from Institute of Economic Research, Seoul National University Contact information at EDIRC.
Bibliographic data for series maintained by Hojung Lee ().