A Vertex Oriented Approach to Minimum Cost Spanning Tree Problems

B.B. Ciftci, S.H. Tijs

Research output: Working paperDiscussion paperOther research output

223 Downloads (Pure)

Abstract

In this paper we consider spanning tree problems, where n players want to be connected to a source as cheap as possible. We introduce and analyze (n!) vertex oriented construct and charge procedures for such spanning tree situations leading in n steps to a minimum cost spanning tree and a cost sharing where each player pays the edge which he chooses in the procedure. The main result of the paper is that the average of the n! cost sharings provided by our procedure is equal to the P-value for minimum cost spanning tree situations introduced and characterized by Branzei et al. (2004). As a side product, we find a new method, the vertex oriented procedure, to construct minimum cost spanning trees.
Original languageEnglish
Place of PublicationTilburg
PublisherOperations research
Number of pages18
Volume2007-89
Publication statusPublished - 2007

Publication series

NameCentER Discussion Paper
Volume2007-89

Keywords

  • Minimum cost spanning tree games
  • algorithm
  • value
  • cost sharing

Fingerprint Dive into the research topics of 'A Vertex Oriented Approach to Minimum Cost Spanning Tree Problems'. Together they form a unique fingerprint.

Cite this