{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,28]],"date-time":"2026-02-28T16:43:10Z","timestamp":1772296990325,"version":"3.50.1"},"publisher-location":"Berlin, Heidelberg","reference-count":11,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783540784975","type":"print"},{"value":"9783540784999","type":"electronic"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"DOI":"10.1007\/978-3-540-78499-9_2","type":"book-chapter","created":{"date-parts":[[2008,4,1]],"date-time":"2008-04-01T23:02:25Z","timestamp":1207090945000},"page":"5-19","source":"Crossref","is-referenced-by-count":13,"title":["Simple Stochastic Games with Few Random Vertices Are Easy to Solve"],"prefix":"10.1007","author":[{"given":"Hugo","family":"Gimbert","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Florian","family":"Horn","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"2_CR1","doi-asserted-by":"publisher","first-page":"203","DOI":"10.1016\/0890-5401(92)90048-K","volume":"96","author":"A. Condon","year":"1992","unstructured":"Condon, A.: The complexity of stochastic games. Information and Computation\u00a096, 203\u2013224 (1992)","journal-title":"Information and Computation"},{"key":"2_CR2","doi-asserted-by":"crossref","unstructured":"Condon, A.: On algorithms for simple stochastic games. In: Advances in computational complexity theory. DIMACS series in discrete mathematics and theoretical computer science, vol.\u00a013, pp. 51\u201373 (1993)","DOI":"10.1090\/dimacs\/013\/04"},{"key":"2_CR3","volume-title":"Finite State Markov Decision Processes","author":"C. Derman","year":"1972","unstructured":"Derman, C.: Finite State Markov Decision Processes. Academic Press, London (1972)"},{"key":"2_CR4","doi-asserted-by":"publisher","first-page":"137","DOI":"10.1007\/BF01459082","volume":"40","author":"J.D. Dixon","year":"1982","unstructured":"Dixon, J.D.: Exact solution of linear equations using p-adic expansions. Numerische Mathematik\u00a040, 137\u2013141 (1982)","journal-title":"Numerische Mathematik"},{"key":"2_CR5","unstructured":"Gimbert, H., Horn, F.: Solving simple stochastic games with few random vertices, http:\/\/hal.archives-ouvertes.fr\/hal-00195914\/fr\/"},{"key":"2_CR6","doi-asserted-by":"publisher","first-page":"37","DOI":"10.1007\/s00453-007-0175-3","volume":"49","author":"N. Halman","year":"2007","unstructured":"Halman, N.: Simple stochastic games, parity games, mean payoff games and discounted payoff games are all LP-type problems. Algorithmica\u00a049, 37\u201350 (2007)","journal-title":"Algorithmica"},{"key":"2_CR7","first-page":"191","volume":"20","author":"L.G. Kachiyan","year":"1979","unstructured":"Kachiyan, L.G.: A polynomial time algorithm for linear programming. Soviet Math. Dokl.\u00a020, 191\u2013194 (1979)","journal-title":"Soviet Math. Dokl."},{"key":"2_CR8","doi-asserted-by":"publisher","first-page":"151","DOI":"10.1006\/inco.1995.1035","volume":"117","author":"W. Ludwig","year":"1995","unstructured":"Ludwig, W.: A subexponential randomized algorithm for the simple stochastic game problem. Information and Computation\u00a0117, 151\u2013155 (1995)","journal-title":"Information and Computation"},{"key":"2_CR9","doi-asserted-by":"publisher","first-page":"59","DOI":"10.1007\/BF01580724","volume":"40","author":"J. Renegar","year":"1988","unstructured":"Renegar, J.: A polynomial-time algorithm, based on newton\u2019s method, for linear programming. Mathematical Programming\u00a040, 59\u201393 (1988)","journal-title":"Mathematical Programming"},{"key":"2_CR10","doi-asserted-by":"crossref","unstructured":"Shapley, L.S.: Stochastic games. In: Proceedings of the National Academy of Science USA, vol.\u00a039, pp. 1095\u20131100 (1953)","DOI":"10.1073\/pnas.39.10.1953"},{"issue":"1","key":"2_CR11","doi-asserted-by":"publisher","first-page":"51","DOI":"10.1016\/j.entcs.2004.07.008","volume":"119","author":"R. Somla","year":"2005","unstructured":"Somla, R.: New algorithms for solving simple stochastic games. Electr. Notes Theor. Comput. Sci.\u00a0119(1), 51\u201365 (2005)","journal-title":"Electr. Notes Theor. Comput. Sci."}],"container-title":["Lecture Notes in Computer Science","Foundations of Software Science and Computational Structures"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-540-78499-9_2.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,4,27]],"date-time":"2021-04-27T11:11:30Z","timestamp":1619521890000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-540-78499-9_2"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[null]]},"ISBN":["9783540784975","9783540784999"],"references-count":11,"URL":"https:\/\/doi.org\/10.1007\/978-3-540-78499-9_2","relation":{},"subject":[]}}