Graph-theoretic game and its application to the k-server problem

This paper investigates a zero-sum game played on a weighted connected graph G between two players, the tree player and the edge player. The game arises in connection with the k-server problem on a road network; i.e., a metric space that can be represented as a multigraph G in which each edge e represents a road of length w(e). Central to the analysis of the game is an algorithm that provides an approximate solution for the simple network design problem. The result has potential application to the design of communication networks. It also improves substantially known estimates concerning the existence of a sparse basis for the cycle space of a graph.