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

Noga Alon, Richard M. Karp, David Peleg, Douglas West

Research output: Contribution to journalArticlepeer-review

210 Scopus citations

Abstract

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.

Original languageEnglish (US)
Pages (from-to)78-100
Number of pages23
JournalSIAM Journal on Computing
Volume24
Issue number1
DOIs
StatePublished - 1995
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • General Computer Science
  • General Mathematics

Fingerprint

Dive into the research topics of 'Graph-theoretic game and its application to the k-server problem'. Together they form a unique fingerprint.

Cite this