The complexity of mean payoff games on graphs
作者： Uri Zwick , Mike Paterson
DOI: 10.1016/0304-3975(95)00188-3
关键词:
摘要: Abstract We study the complexity of finding values and optimal strategies mean payoff games on graphs, a family perfect information introduced by Ehrenfeucht Mycielski considered Gurvich, Karzanov Khachiyan. describe pseudo-polynomial-time algorithm for solution such games, decision problem which is in NP ∩ coNP . Finally, we polynomial reduction from to simple stochastic studied Condon. These are also known be , but no or them.
core.ac.uk
acm.org
elsevier.com
sci-hub.se 参考文章(22)
J.I. Munro, M.S. Paterson, Selection and sorting with limited storage Theoretical Computer Science. ,vol. 12, pp. 315- 323 ,(1980) , 10.1016/0304-3975(80)90061-4
Hans L. Bodlaender, Complexity of path-forming games Theoretical Computer Science. ,vol. 110, pp. 215- 245 ,(1993) , 10.1016/0304-3975(93)90357-Y
V.A. Gurvich, A.V. Karzanov, L.G. Khachivan, Cyclic games and an algorithm to find minimax cycle means in directed graphs Ussr Computational Mathematics and Mathematical Physics. ,vol. 28, pp. 85- 91 ,(1990) , 10.1016/0041-5553(88)90012-2
P. Butkovic, R.A. Cuninghame-Green, An O( n 2 ) algorithm for the maximum cycle mean of an n x n bivalent matrix Discrete Applied Mathematics. ,vol. 35, pp. 157- 162 ,(1992) , 10.1016/0166-218X(92)90039-D
Alexander V. Karzanov, Vasilij N. Lebedev, Cyclical games with prohibitions Mathematical Programming. ,vol. 60, pp. 277- 293 ,(1993) , 10.1007/BF01580616
Richard M. Karp, A characterization of the minimum cycle mean in a digraph Discrete Mathematics. ,vol. 23, pp. 309- 311 ,(1978) , 10.1016/0012-365X(78)90011-0
Vaughan R. Pratt, Every Prime Has a Succinct Certificate SIAM Journal on Computing. ,vol. 4, pp. 214- 220 ,(1975) , 10.1137/0204018
Aviezri S Fraenkel, Edward R Scheinerman, Daniel Ullman, Undirected edge geography Theoretical Computer Science. ,vol. 112, pp. 371- 381 ,(1993) , 10.1016/0304-3975(93)90026-P
W. Ludwig, A Subexponential Randomized Algorithm for the Simple Stochastic Game Problem Information & Computation. ,vol. 117, pp. 151- 155 ,(1995) , 10.1006/INCO.1995.1035
James B. Orlin, Ravindra K. Ahuja, New scaling algorithms for the assignment and minimum mean cycle problems Mathematical Programming. ,vol. 54, pp. 41- 56 ,(1992) , 10.1007/BF01586040