The Library
The complexity of mean payoff games on graphs
Tools
Tools
Tools
UNSPECIFIED (1996) The complexity of mean payoff games on graphs. THEORETICAL COMPUTER SCIENCE, 158 (1-2). pp. 343-359. ISSN 0304-3975
Full text not available from this repository.Abstract
We study the complexity of finding the values and optimal strategies of mean payoff games on graphs, a family of perfect information games introduced by Ehrenfeucht and Mycielski and considered by Gurvich, Karzanov and Khachiyan. We describe a pseudo-polynomial-time algorithm for the solution of such games, the decision problem for which is in NP boolean AND coNP. Finally, we describe a polynomial reduction from mean payoff games to the simple stochastic games studied by Condon. These games are also known to be in NP boolean AND coNP, but no polynomial or pseudo-polynomial-time algorithm is known for them.
| Item Type: | Journal Article |
|---|---|
| Subjects: | Q Science > QA Mathematics > QA76 Electronic computers. Computer science. Computer software |
| Journal or Publication Title: | THEORETICAL COMPUTER SCIENCE |
| Publisher: | ELSEVIER SCIENCE BV |
| ISSN: | 0304-3975 |
| Date: | 20 May 1996 |
| Volume: | 158 |
| Number: | 1-2 |
| Number of Pages: | 17 |
| Page Range: | pp. 343-359 |
| Publication Status: | Published |
| URI: | http://wrap.warwick.ac.uk/id/eprint/18818 |
Data sourced from Thomson Reuters' Web of Knowledge
Actions (login required)
 |
View Item |
