{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,9,24]],"date-time":"2026-09-24T12:09:32Z","timestamp":1790251772319,"version":"4.1.0"},"publisher-location":"Berlin, Heidelberg","reference-count":26,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783662480533","type":"print"},{"value":"9783662480540","type":"electronic"}],"license":[{"start":{"date-parts":[[2015,1,1]],"date-time":"2015-01-01T00:00:00Z","timestamp":1420070400000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2015]]},"DOI":"10.1007\/978-3-662-48054-0_28","type":"book-chapter","created":{"date-parts":[[2015,8,10]],"date-time":"2015-08-10T07:57:29Z","timestamp":1439193449000},"page":"336-347","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":4,"title":["Parameterized Algorithms for Parity Games"],"prefix":"10.1007","author":[{"given":"Jakub","family":"Gajarsk\u00fd","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Michael","family":"Lampis","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Kazuhisa","family":"Makino","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Valia","family":"Mitsou","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Sebastian","family":"Ordyniak","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2015,8,11]]},"reference":[{"issue":"4","key":"28_CR1","doi-asserted-by":"publisher","first-page":"900","DOI":"10.1016\/j.jctb.2012.04.004","volume":"102","author":"D Berwanger","year":"2012","unstructured":"Berwanger, D., Dawar, A., Hunter, P., Kreutzer, S., Obdr\u017e\u00e1lek, J.: The dag-width of directed graphs. J. Comb. Theo. Ser. B 102(4), 900\u2013923 (2012)","journal-title":"J. Comb. Theo. Ser. B"},{"key":"28_CR2","doi-asserted-by":"publisher","first-page":"2","DOI":"10.1016\/j.tcs.2012.07.010","volume":"463","author":"D Berwanger","year":"2012","unstructured":"Berwanger, D., Gr\u00e4del, E., Kaiser, L., Rabinovich, R.: Entanglement and the complexity of directed graphs. Theor. Comput. Sci. 463, 2\u201325 (2012)","journal-title":"Theor. Comput. Sci."},{"key":"28_CR3","unstructured":"Bjorklund, H., Sandberg, S., Vorobyov, S.: On fixed-parameter complexity of infinite games. In: Sere, K., Wald\u00e9n, M. (eds.) The Nordic Workshop on Programming Theory (NWPT 2003), number 34 in \u00c5bo Akademi, Reports on Computer Science and Mathematics, pp. 29\u201331. Citeseer (2003)"},{"issue":"1\u20133","key":"28_CR4","doi-asserted-by":"publisher","first-page":"365","DOI":"10.1016\/S0304-3975(03)00427-4","volume":"310","author":"H Bj\u00f6rklund","year":"2004","unstructured":"Bj\u00f6rklund, H., Sandberg, S., Vorobyov, S.G.: Memoryless determinacy of parity and mean payoff games: a simple proof. Theor. Comput. Sci. 310(1\u20133), 365\u2013378 (2004)","journal-title":"Theor. Comput. Sci."},{"issue":"2","key":"28_CR5","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 Appl. Math. 155(2), 210\u2013229 (2007)","journal-title":"Discrete Appl. Math."},{"key":"28_CR6","unstructured":"Bojanczyk, M., Dittmann, C., Kreutzer, S.: Decomposition theorems and model-checking for the modal $$\\mu $$-calculus. In: Henzinger, T.A., Miller, D. (eds.) Joint Meeting of the Twenty-Third EACSL Annual Conference on Computer Science Logic (CSL) and the Twenty-Ninth Annual ACM\/IEEE Symposium on Logic in Computer Science (LICS), CSL-LICS 2014, Vienna, Austria, July 14\u201318, 2014, p. 17. ACM (2014)"},{"issue":"1\u20132","key":"28_CR7","doi-asserted-by":"publisher","first-page":"237","DOI":"10.1016\/S0304-3975(96)00228-9","volume":"178","author":"A Browne","year":"1997","unstructured":"Browne, A., Clarke, E.M., Jha, S., Long, D.E., Marrero, W.R.: An improved algorithm for the evaluation of fixpoint expressions. Theor. Comput. Sci. 178(1\u20132), 237\u2013255 (1997)","journal-title":"Theor. Comput. Sci."},{"issue":"2","key":"28_CR8","doi-asserted-by":"publisher","first-page":"394","DOI":"10.1016\/j.jcss.2011.05.002","volume":"78","author":"K Chatterjee","year":"2012","unstructured":"Chatterjee, K., Henzinger, T.A.: A survey of stochastic $$\\omega $$-regular games. J. Comput. Syst. Sci. 78(2), 394\u2013413 (2012)","journal-title":"J. Comput. Syst. Sci."},{"issue":"2","key":"28_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. Inf. Comput. 96(2), 203\u2013224 (1992)","journal-title":"Inf. Comput."},{"key":"28_CR10","unstructured":"Dittmann, C., Kreutzer, S., Tomescu, A.I.: Graph operations on parity games and polynomial-time algorithms. arXiv preprint (2012). arXiv:1208.1640"},{"issue":"1","key":"28_CR11","doi-asserted-by":"publisher","first-page":"132","DOI":"10.1137\/S0097539793304741","volume":"29","author":"EA Emerson","year":"1999","unstructured":"Emerson, E.A., Jutla, C.S.: The complexity of tree automata and logics of programs. SIAM J. Comput. 29(1), 132\u2013158 (1999)","journal-title":"SIAM J. Comput."},{"issue":"1\u20132","key":"28_CR12","doi-asserted-by":"publisher","first-page":"491","DOI":"10.1016\/S0304-3975(00)00034-7","volume":"258","author":"EA Emerson","year":"2001","unstructured":"Emerson, E.A., Jutla, C.S., Sistla, A.P.: On model checking for the $$\\mu $$-calculus and its fragments. Theor. Comput. Sci. 258(1\u20132), 491\u2013522 (2001)","journal-title":"Theor. Comput. Sci."},{"key":"28_CR13","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"182","DOI":"10.1007\/978-3-319-08404-6_16","volume-title":"Algorithm Theory \u2013 SWAT 2014","author":"FV Fomin","year":"2014","unstructured":"Fomin, F.V., Liedloff, M., Montealegre, P., Todinca, I.: Algorithms parameterized by vertex cover and modular width, through potential maximal cliques. In: Ravi, R., G\u00f8rtz, I.L. (eds.) SWAT 2014. LNCS, vol. 8503, pp. 182\u2013193. Springer, Heidelberg (2014)"},{"key":"28_CR14","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"163","DOI":"10.1007\/978-3-319-03898-8_15","volume-title":"Parameterized and Exact Computation","author":"J Gajarsk\u00fd","year":"2013","unstructured":"Gajarsk\u00fd, J., Lampis, M., Ordyniak, S.: Parameterized algorithms for modular-width. In: Gutin, G., Szeider, S. (eds.) IPEC 2013. LNCS, vol. 8246, pp. 163\u2013176. Springer, Heidelberg (2013)"},{"key":"28_CR15","series-title":"Lecture Notes in Computer Science","volume-title":"Automata, Logics, and Infinite Games: A Guide to Current Research","year":"2002","unstructured":"Gr\u00e4del, E., Thomas, W., Wilke, T. (eds.): Automata, Logics, and Infinite Games: A Guide to Current Research. LNCS, vol. 2500. Springer, Heidelberg (2002)"},{"issue":"3","key":"28_CR16","doi-asserted-by":"publisher","first-page":"206","DOI":"10.1016\/j.tcs.2008.02.038","volume":"399","author":"P Hunter","year":"2008","unstructured":"Hunter, P., Kreutzer, S.: Digraph measures: kelly decompositions, games, and orderings. Theor. Comput. Sci. 399(3), 206\u2013219 (2008)","journal-title":"Theor. Comput. Sci."},{"issue":"3","key":"28_CR17","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 cap co-up. Inf. Process. Lett. 68(3), 119\u2013124 (1998)","journal-title":"Inf. Process. Lett."},{"key":"28_CR18","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"290","DOI":"10.1007\/3-540-46541-3_24","volume-title":"STACS 2000","author":"M Jurdzi\u0144ski","year":"2000","unstructured":"Jurdzi\u0144ski, M.: Small progress measures for solving parity games. In: Reichel, H., Tison, S. (eds.) STACS 2000. LNCS, vol. 1770, pp. 290\u2013301. Springer, Heidelberg (2000)"},{"issue":"4","key":"28_CR19","doi-asserted-by":"publisher","first-page":"1519","DOI":"10.1137\/070686652","volume":"38","author":"M Jurdzinski","year":"2008","unstructured":"Jurdzinski, M., Paterson, M., Zwick, U.: A deterministic subexponential algorithm for solving parity games. SIAM J. Comput. 38(4), 1519\u20131532 (2008)","journal-title":"SIAM J. Comput."},{"key":"28_CR20","series-title":"LNCS","doi-asserted-by":"publisher","first-page":"95","DOI":"10.1007\/3-540-36387-4_6","volume-title":"Automata Logics, and Infinite Games","author":"R K\u00fcsters","year":"2002","unstructured":"K\u00fcsters, R.: Memoryless determinacy of parity games. In: Gr\u00e4del, E., Thomas, W., Wilke, T. (eds.) Automata Logics, and Infinite Games. LNCS, vol. 2500, pp. 95\u2013106. Springer, Heidelberg (2002)"},{"issue":"2","key":"28_CR21","doi-asserted-by":"publisher","first-page":"149","DOI":"10.1016\/0168-0072(93)90036-D","volume":"65","author":"R McNaughton","year":"1993","unstructured":"McNaughton, R.: Infinite games played on finite graphs. Ann. Pure Appl. Logic 65(2), 149\u2013184 (1993)","journal-title":"Ann. Pure Appl. Logic"},{"key":"28_CR22","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"80","DOI":"10.1007\/978-3-540-45069-6_7","volume-title":"Computer Aided Verification","author":"J Obdr\u017e\u00e1lek","year":"2003","unstructured":"Obdr\u017e\u00e1lek, J.: Fast mu-calculus model checking when tree-width is bounded. In: Hunt Jr., W.A., Somenzi, F. (eds.) CAV 2003. LNCS, vol. 2725, pp. 80\u201392. Springer, Heidelberg (2003)"},{"key":"28_CR23","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. 4646, pp. 54\u201368. Springer, Heidelberg (2007)"},{"key":"28_CR24","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"449","DOI":"10.1007\/978-3-540-77050-3_37","volume-title":"FSTTCS 2007: Foundations of Software Technology and Theoretical Computer Science","author":"S Schewe","year":"2007","unstructured":"Schewe, S.: Solving parity games in big steps. In: Arvind, V., Prasad, S. (eds.) FSTTCS 2007. LNCS, vol. 4855, pp. 449\u2013460. Springer, Heidelberg (2007)"},{"issue":"1\u20132","key":"28_CR25","doi-asserted-by":"publisher","first-page":"135","DOI":"10.1016\/S0304-3975(98)00009-7","volume":"200","author":"W Zielonka","year":"1998","unstructured":"Zielonka, W.: Infinite games on finitely coloured graphs with applications to automata on infinite trees. Theor. Comput. Sci. 200(1\u20132), 135\u2013183 (1998)","journal-title":"Theor. Comput. Sci."},{"issue":"1&2","key":"28_CR26","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. Theor. Comput. Sci. 158(1&2), 343\u2013359 (1996)","journal-title":"Theor. Comput. Sci."}],"container-title":["Lecture Notes in Computer Science","Mathematical Foundations of Computer Science 2015"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-662-48054-0_28","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,2,8]],"date-time":"2023-02-08T09:19:14Z","timestamp":1675847954000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-662-48054-0_28"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015]]},"ISBN":["9783662480533","9783662480540"],"references-count":26,"URL":"https:\/\/doi.org\/10.1007\/978-3-662-48054-0_28","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2015]]},"assertion":[{"value":"11 August 2015","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}}]}}