{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,19]],"date-time":"2026-06-19T18:20:33Z","timestamp":1781893233822,"version":"3.54.5"},"reference-count":11,"publisher":"Springer Science and Business Media LLC","issue":"4","license":[{"start":{"date-parts":[[2016,2,2]],"date-time":"2016-02-02T00:00:00Z","timestamp":1454371200000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"funder":[{"name":"Department of Computer Science, University of Verona, Verona, Italy","award":["Ph.D. grant \u201cComputational Mathematics and Biology\u201d"],"award-info":[{"award-number":["Ph.D. grant \u201cComputational Mathematics and Biology\u201d"]}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2017,4]]},"DOI":"10.1007\/s00453-016-0123-1","type":"journal-article","created":{"date-parts":[[2016,2,2]],"date-time":"2016-02-02T15:41:50Z","timestamp":1454427710000},"page":"995-1021","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":12,"title":["Improved Pseudo-polynomial Bound for the Value Problem and Optimal Strategy Synthesis in Mean Payoff Games"],"prefix":"10.1007","volume":"77","author":[{"given":"Carlo","family":"Comin","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Romeo","family":"Rizzi","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2016,2,2]]},"reference":[{"key":"123_CR1","unstructured":"Andersson, D., Vorobyov, S.: Fast algorithms for monotonic discounted linear programs with two variables per inequality. Tech. rep., Preprint NI06019-LAA, Isaac Netwon Institute for Mathematical Sciences, Cambridge, UK (2006)"},{"key":"123_CR2","doi-asserted-by":"crossref","first-page":"33","DOI":"10.1007\/978-3-540-85778-5_4","volume-title":"Formal Modeling and Analysis of Timed Systems, Lecture Notes in Computer Science","author":"P Bouyer","year":"2008","unstructured":"Bouyer, P., Fahrenberg, U., Larsen, K., Markey, N., Srba, J.: Infinite runs in weighted timed automata with energy constraints. In: Cassez, F., Jard, C. (eds.) Formal Modeling and Analysis of Timed Systems, Lecture Notes in Computer Science, vol. 5215, pp. 33\u201347. Springer, Berlin (2008)"},{"issue":"2","key":"123_CR3","doi-asserted-by":"crossref","first-page":"97","DOI":"10.1007\/s10703-010-0105-x","volume":"38","author":"L Brim","year":"2011","unstructured":"Brim, L., Chaloupka, J., Doyen, L., Gentilini, R., Raskin, J.: Faster algorithms for mean-payoff games. Form. Methods Syst. Des. 38(2), 97\u2013118 (2011)","journal-title":"Form. Methods Syst. Des."},{"key":"123_CR4","first-page":"117","volume-title":"Embedded Software, Lecture Notes in Computer Science","author":"A Chakrabarti","year":"2003","unstructured":"Chakrabarti, A., de Alfaro, L., Henzinger, T., Stoelinga, M.: Resource interfaces. In: Alur, R., Lee, I. (eds.) Embedded Software, Lecture Notes in Computer Science, vol. 2855, pp. 117\u2013133. Springer, Berlin (2003)"},{"issue":"2","key":"123_CR5","doi-asserted-by":"crossref","first-page":"109","DOI":"10.1007\/BF01768705","volume":"8","author":"A Ehrenfeucht","year":"1979","unstructured":"Ehrenfeucht, A., Mycielski, J.: Positional strategies for mean payoff games. Int. J. Game Theory 8(2), 109\u2013113 (1979)","journal-title":"Int. J. Game Theory"},{"key":"123_CR6","volume-title":"Concrete Mathematics: A Foundation for Computer Science","author":"R Graham","year":"1994","unstructured":"Graham, R., Knuth, D., Patashnik, O.: Concrete Mathematics: A Foundation for Computer Science, 2nd edn. Addison-Wesley Longman Publishing Co., Inc, Boston (1994)","edition":"2"},{"issue":"5","key":"123_CR7","doi-asserted-by":"crossref","first-page":"85","DOI":"10.1016\/0041-5553(88)90012-2","volume":"28","author":"V Gurvich","year":"1988","unstructured":"Gurvich, V., Karzanov, A., Khachiyan, L.: Cyclic games and an algorithm to find minimax cycle means in directed graphs. USSR Comput. Math. Math. Phys. 28(5), 85\u201391 (1988)","journal-title":"USSR Comput. Math. Math. Phys."},{"issue":"3","key":"123_CR8","doi-asserted-by":"crossref","first-page":"119","DOI":"10.1016\/S0020-0190(98)00150-1","volume":"68","author":"M Jurdzi\u0144ski","year":"1998","unstructured":"Jurdzi\u0144ski, M.: Deciding the winner in parity games is in UP $$\\cap $$ \u2229 co-UP. Inf. Process. Lett. 68(3), 119\u2013124 (1998)","journal-title":"Inf. Process. Lett."},{"issue":"3","key":"123_CR9","doi-asserted-by":"crossref","first-page":"4967","DOI":"10.1007\/s10958-007-0331-y","volume":"145","author":"Y Lifshits","year":"2007","unstructured":"Lifshits, Y., Pavlov, D.: Potential theory for mean payoff games. J. Math. Sci. 145(3), 4967\u20134974 (2007)","journal-title":"J. Math. Sci."},{"issue":"2","key":"123_CR10","doi-asserted-by":"crossref","first-page":"271","DOI":"10.1007\/s00453-008-9221-z","volume":"55","author":"J Pawlewicz","year":"2009","unstructured":"Pawlewicz, J., P\u0103tra\u015fcu, M.: Order statistics in the farey sequences in sublinear time and counting primitive lattice points in polygons. Algorithmica 55(2), 271\u2013282 (2009)","journal-title":"Algorithmica"},{"key":"123_CR11","doi-asserted-by":"crossref","first-page":"343","DOI":"10.1016\/0304-3975(95)00188-3","volume":"158","author":"U Zwick","year":"1996","unstructured":"Zwick, U., Paterson, M.: The complexity of mean payoff games on graphs. Theor. Comput. Sci. 158, 343\u2013359 (1996)","journal-title":"Theor. Comput. Sci."}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-016-0123-1.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00453-016-0123-1\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-016-0123-1","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-016-0123-1.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,28]],"date-time":"2019-05-28T19:47:23Z","timestamp":1559072843000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00453-016-0123-1"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016,2,2]]},"references-count":11,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2017,4]]}},"alternative-id":["123"],"URL":"https:\/\/doi.org\/10.1007\/s00453-016-0123-1","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[2016,2,2]]}}}