Representation of Ultrametric Minimum Cost Spanning Tree Games as Cost Allocation Games on Rooted Trees

A minimum cost spanning tree game is called ultrametric if the cost function on the edges of the underlying network is an ultrametric. We show that every ultra-metric minimum cost spanning tree game is represented as a (-ost allocation game on a rooted tree and give an $O(??^{2}) $ time algorithm to find su$(.h $ a representation, where $?l $ is the number of plavers. Using the known results on the time complexity of solutions of cost allocation games on rooted trees, we then show that there ex-ist $O(\uparrow?^{2}) $ time algorithms for computing the Shapley value, the nucleolus and the $c- galitaJ^{\cdot}iail $ allocation of the ultrametric minimum cost spanning tree games.