{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,7]],"date-time":"2024-09-07T09:34:10Z","timestamp":1725701650568},"publisher-location":"Berlin, Heidelberg","reference-count":24,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642330896"},{"type":"electronic","value":"9783642330902"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2012]]},"DOI":"10.1007\/978-3-642-33090-2_27","type":"book-chapter","created":{"date-parts":[[2012,8,28]],"date-time":"2012-08-28T15:29:11Z","timestamp":1346167751000},"page":"301-312","source":"Crossref","is-referenced-by-count":3,"title":["Polynomial-Time Algorithms for Energy Games with Special Weight Structures"],"prefix":"10.1007","author":[{"given":"Krishnendu","family":"Chatterjee","sequence":"first","affiliation":[]},{"given":"Monika","family":"Henzinger","sequence":"additional","affiliation":[]},{"given":"Sebastian","family":"Krinninger","sequence":"additional","affiliation":[]},{"given":"Danupon","family":"Nanongkai","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"27_CR1","unstructured":"Beffara, E., Vorobyov, S.: Is Randomized Gurvich-Karzanov-Khachiyan\u2019s Algorithm for Parity Games Polynomial? Tech. Rep. 2001-025, Department of Information Technology, Uppsala University (October 2001)"},{"issue":"2","key":"27_CR2","doi-asserted-by":"publisher","first-page":"210","DOI":"10.1016\/j.dam.2006.04.029","volume":"155","author":"H. Bj\u00f6rklund","year":"2007","unstructured":"Bj\u00f6rklund, H., Vorobyov, S.G.: A combinatorial strongly subexponential strategy improvement algorithm for mean payoff games. Discrete Applied Mathematics\u00a0155(2), 210\u2013229 (2007)","journal-title":"Discrete Applied Mathematics"},{"key":"27_CR3","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"140","DOI":"10.1007\/978-3-642-02658-4_14","volume-title":"Computer Aided Verification","author":"R. Bloem","year":"2009","unstructured":"Bloem, R., Chatterjee, K., Henzinger, T.A., Jobstmann, B.: Better Quality in Synthesis through Quantitative Objectives. In: Bouajjani, A., Maler, O. (eds.) CAV 2009. LNCS, vol.\u00a05643, pp. 140\u2013156. Springer, Heidelberg (2009)"},{"key":"27_CR4","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"147","DOI":"10.1007\/978-3-642-22006-7_13","volume-title":"Automata, Languages and Programming","author":"E. Boros","year":"2011","unstructured":"Boros, E., Elbassioni, K., Fouz, M., Gurvich, V., Makino, K., Manthey, B.: Stochastic Mean Payoff Games: Smoothed\u00a0Analysis\u00a0and\u00a0Approximation\u00a0Schemes. In: Aceto, L., Henzinger, M., Sgall, J. (eds.) ICALP 2011. LNCS, vol.\u00a06755, pp. 147\u2013158. Springer, Heidelberg (2011)"},{"key":"27_CR5","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"33","DOI":"10.1007\/978-3-540-85778-5_4","volume-title":"Formal Modeling and Analysis of Timed Systems","author":"P. Bouyer","year":"2008","unstructured":"Bouyer, P., Fahrenberg, U., Larsen, K.G., Markey, N., Srba, J.: Infinite Runs in Weighted Timed Automata with Energy Constraints. In: Cassez, F., Jard, C. (eds.) FORMATS 2008. LNCS, vol.\u00a05215, pp. 33\u201347. Springer, Heidelberg (2008)"},{"issue":"2","key":"27_CR6","doi-asserted-by":"publisher","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.F.: Faster algorithms for mean-payoff games. Formal Methods in System Design\u00a038(2), 97\u2013118 (2011)","journal-title":"Formal Methods in System Design"},{"key":"27_CR7","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"243","DOI":"10.1007\/978-3-642-22110-1_20","volume-title":"Computer Aided Verification","author":"P. \u010cern\u00fd","year":"2011","unstructured":"\u010cern\u00fd, P., Chatterjee, K., Henzinger, T.A., Radhakrishna, A., Singh, R.: Quantitative Synthesis for Concurrent Programs. In: Gopalakrishnan, G., Qadeer, S. (eds.) CAV 2011. LNCS, vol.\u00a06806, pp. 243\u2013259. Springer, Heidelberg (2011)"},{"key":"27_CR8","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"117","DOI":"10.1007\/978-3-540-45212-6_9","volume-title":"Embedded Software","author":"A. Chakrabarti","year":"2003","unstructured":"Chakrabarti, A., de Alfaro, L., Henzinger, T.A., Stoelinga, M.: Resource Interfaces. In: Alur, R., Lee, I. (eds.) EMSOFT 2003. LNCS, vol.\u00a02855, pp. 117\u2013133. Springer, Heidelberg (2003)"},{"issue":"2","key":"27_CR9","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(2), 203\u2013224 (1992)","journal-title":"Information and Computation"},{"key":"27_CR10","doi-asserted-by":"crossref","unstructured":"Daskalakis, C., Papadimitriou, C.H.: Continuous Local Search. In: SODA, pp. 790\u2013804 (2011)","DOI":"10.1137\/1.9781611973082.62"},{"issue":"2","key":"27_CR11","doi-asserted-by":"publisher","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. International Journal of Game Theory\u00a08(2), 109\u2013113 (1979)","journal-title":"International Journal of Game Theory"},{"key":"27_CR12","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"192","DOI":"10.1007\/978-3-642-20807-2_16","volume-title":"Integer Programming and Combinatoral Optimization","author":"O. Friedmann","year":"2011","unstructured":"Friedmann, O.: A Subexponential Lower Bound for Zadeh\u2019s Pivoting Rule for Solving Linear Programs and Games. In: G\u00fcnl\u00fck, O., Woeginger, G.J. (eds.) IPCO 2011. LNCS, vol.\u00a06655, pp. 192\u2013206. Springer, Heidelberg (2011)"},{"key":"27_CR13","doi-asserted-by":"crossref","unstructured":"Friedmann, O., Hansen, T.D., Zwick, U.: A subexponential lower bound for the Random Facet algorithm for Parity Games. In: SODA, pp. 202\u2013216 (2011)","DOI":"10.1137\/1.9781611973082.19"},{"key":"27_CR14","doi-asserted-by":"crossref","unstructured":"Friedmann, O., Hansen, T.D., Zwick, U.: Subexponential lower bounds for randomized pivoting rules for the simplex algorithm. In: STOC, pp. 283\u2013292 (2011)","DOI":"10.1145\/1993636.1993675"},{"key":"27_CR15","unstructured":"Gentilini, R.: A Note on the Approximation of Mean-Payoff Games. In: CILC (2011)"},{"issue":"5","key":"27_CR16","doi-asserted-by":"publisher","first-page":"85","DOI":"10.1016\/0041-5553(88)90012-2","volume":"28","author":"V.A. Gurvich","year":"1990","unstructured":"Gurvich, V.A., Karzanov, A.V., Khachiyan, L.G.: Cyclic games and an algorithm to find minimax cycle means in directed graphs. USSR Computational Mathematics and Mathematical Physics\u00a028(5), 85\u201391 (1990)","journal-title":"USSR Computational Mathematics and Mathematical Physics"},{"issue":"1","key":"27_CR17","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(1), 37\u201350 (2007)","journal-title":"Algorithmica"},{"issue":"3","key":"27_CR18","doi-asserted-by":"publisher","first-page":"119","DOI":"10.1016\/S0020-0190(98)00150-1","volume":"68","author":"M. Jurdzinski","year":"1998","unstructured":"Jurdzinski, M.: Deciding the Winner in Parity Games is in UP\u2009\u2229\u2009co\u2212UP. Inf. Process. Lett.\u00a068(3), 119\u2013124 (1998)","journal-title":"Inf. Process. Lett."},{"issue":"4","key":"27_CR19","first-page":"525","volume":"44","author":"V.N. Lebedev","year":"2005","unstructured":"Lebedev, V.N.: Effectively Solvable Classes of Cyclical Games. Journal of Computer and Systems Sciences International\u00a044(4), 525\u2013530 (2005)","journal-title":"Journal of Computer and Systems Sciences International"},{"issue":"2","key":"27_CR20","doi-asserted-by":"publisher","first-page":"363","DOI":"10.2307\/1971035","volume":"102","author":"D.A. Martin","year":"1975","unstructured":"Martin, D.A.: Borel determinacy. Annals of Mathematics\u00a0102(2), 363\u2013371 (1975)","journal-title":"Annals of Mathematics"},{"key":"27_CR21","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"54","DOI":"10.1007\/978-3-540-74915-8_8","volume-title":"Computer Science Logic","author":"J. Obdr\u017e\u00e1lek","year":"2007","unstructured":"Obdr\u017e\u00e1lek, J.: Clique-Width and Parity Games. In: Duparc, J., Henzinger, T.A. (eds.) CSL 2007. LNCS, vol.\u00a04646, pp. 54\u201368. Springer, Heidelberg (2007)"},{"key":"27_CR22","doi-asserted-by":"crossref","unstructured":"Roth, A., Balcan, M.F., Kalai, A., Mansour, Y.: On the Equilibria of Alternating Move Games. In: SODA, pp. 805\u2013816 (2010)","DOI":"10.1137\/1.9781611973075.66"},{"issue":"11","key":"27_CR23","doi-asserted-by":"publisher","first-page":"2195","DOI":"10.1016\/j.dam.2008.04.012","volume":"156","author":"S. Vorobyov","year":"2008","unstructured":"Vorobyov, S.: Cyclic games and linear programming. Discrete Applied Mathematics\u00a0156(11), 2195\u20132231 (2008)","journal-title":"Discrete Applied Mathematics"},{"issue":"1&2","key":"27_CR24","doi-asserted-by":"publisher","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. Theoretical Computer Science\u00a0158(1&2), 343\u2013359 (1996), also in COCOON 1995","journal-title":"Theoretical Computer Science"}],"container-title":["Lecture Notes in Computer Science","Algorithms \u2013 ESA 2012"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-33090-2_27.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,5,4]],"date-time":"2021-05-04T11:54:51Z","timestamp":1620129291000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-33090-2_27"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2012]]},"ISBN":["9783642330896","9783642330902"],"references-count":24,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-33090-2_27","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2012]]}}}