A Vertex Oriented Approach to Minimum Cost Spanning Tree Problems

B.B. Ciftci, S.H. Tijs

Research output: Working paperDiscussion paperOther research output

205 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

    Fingerprint

Keywords

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

Cite this

Ciftci, B. B., & Tijs, S. H. (2007). A Vertex Oriented Approach to Minimum Cost Spanning Tree Problems. (CentER Discussion Paper; Vol. 2007-89). Operations research.