The Library
The complexity of mean payoff games on graphs
Tools
UNSPECIFIED (1996) The complexity of mean payoff games on graphs. THEORETICAL COMPUTER SCIENCE, 158 (1-2). pp. 343-359. ISSN 0304-3975.
Research output not available from this repository.
Request-a-Copy directly from author or use local Library Get it For Me service.
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 | ||||
Official Date: | 20 May 1996 | ||||
Dates: |
|
||||
Volume: | 158 | ||||
Number: | 1-2 | ||||
Number of Pages: | 17 | ||||
Page Range: | pp. 343-359 | ||||
Publication Status: | Published |
Data sourced from Thomson Reuters' Web of Knowledge
Request changes or add full text files to a record
Repository staff actions (login required)
View Item |