{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,4]],"date-time":"2024-09-04T15:59:22Z","timestamp":1725465562243},"publisher-location":"Berlin, Heidelberg","reference-count":17,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642382321"},{"type":"electronic","value":"9783642382338"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2013]]},"DOI":"10.1007\/978-3-642-38233-8_2","type":"book-chapter","created":{"date-parts":[[2013,5,15]],"date-time":"2013-05-15T12:57:16Z","timestamp":1368622636000},"page":"13-24","source":"Crossref","is-referenced-by-count":0,"title":["Parameterized Complexity and Kernel Bounds for Hard Planning Problems"],"prefix":"10.1007","author":[{"given":"Christer","family":"B\u00e4ckstr\u00f6m","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Peter","family":"Jonsson","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Sebastian","family":"Ordyniak","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Stefan","family":"Szeider","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"doi-asserted-by":"crossref","unstructured":"B\u00e4ckstr\u00f6m, C., Chen, Y., Jonsson, P., Ordyniak, S., Szeider, S.: The complexity of planning revisited - a parameterized analysis. In: Hoffmann, J., Selman, B. (eds.) Proceedings of the Twenty-Sixth AAAI Conference on Artificial Intelligence, Toronto, Ontario, Canada, July 22-26. AAAI Press (2012)","key":"2_CR1","DOI":"10.1609\/aaai.v26i1.8361"},{"key":"2_CR2","doi-asserted-by":"publisher","first-page":"181","DOI":"10.1111\/j.1467-8640.1991.tb00393.x","volume":"7","author":"C. B\u00e4ckstr\u00f6m","year":"1991","unstructured":"B\u00e4ckstr\u00f6m, C., Klein, I.: Planning in polynomial time: the SAS-PUBS class. Comput. Intelligence\u00a07, 181\u2013197 (1991)","journal-title":"Comput. Intelligence"},{"key":"2_CR3","doi-asserted-by":"publisher","first-page":"625","DOI":"10.1111\/j.1467-8640.1995.tb00052.x","volume":"11","author":"C. B\u00e4ckstr\u00f6m","year":"1995","unstructured":"B\u00e4ckstr\u00f6m, C., Nebel, B.: Complexity results for SAS+ planning. Comput. Intelligence\u00a011, 625\u2013656 (1995)","journal-title":"Comput. Intelligence"},{"issue":"1-2","key":"2_CR4","doi-asserted-by":"publisher","first-page":"165","DOI":"10.1016\/0004-3702(94)90081-7","volume":"69","author":"T. Bylander","year":"1994","unstructured":"Bylander, T.: The computational complexity of propositional STRIPS planning. Artificial Intelligence\u00a069(1-2), 165\u2013204 (1994)","journal-title":"Artificial Intelligence"},{"issue":"8","key":"2_CR5","doi-asserted-by":"publisher","first-page":"423","DOI":"10.1016\/j.jcss.2009.04.001","volume":"75","author":"H.L. Bodlaender","year":"2009","unstructured":"Bodlaender, H.L., Downey, R.G., Fellows, M.R., Hermelin, D.: On problems without polynomial kernels. J. of Computer and System Sciences\u00a075(8), 423\u2013434 (2009)","journal-title":"J. of Computer and System Sciences"},{"key":"2_CR6","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"635","DOI":"10.1007\/978-3-642-04128-0_57","volume-title":"Algorithms - ESA 2009","author":"H.L. Bodlaender","year":"2009","unstructured":"Bodlaender, H.L., Thomass\u00e9, S., Yeo, A.: Kernel bounds for disjoint cycles and disjoint paths. In: Fiat, A., Sanders, P. (eds.) ESA 2009. LNCS, vol.\u00a05757, pp. 635\u2013646. Springer, Heidelberg (2009)"},{"issue":"8","key":"2_CR7","doi-asserted-by":"publisher","first-page":"1346","DOI":"10.1016\/j.jcss.2006.04.007","volume":"72","author":"J. Chen","year":"2006","unstructured":"Chen, J., Huang, X., Kanj, I.A., Xia, G.: Strong computational lower bounds via parameterized complexity. J. of Computer and System Sciences\u00a072(8), 1346\u20131367 (2006)","journal-title":"J. of Computer and System Sciences"},{"doi-asserted-by":"crossref","unstructured":"Downey, R., Fellows, M.R., Stege, U.: Parameterized complexity: A framework for systematically confronting computational intractability. In: Contemporary Trends in Discrete Mathematics: From DIMACS and DIMATIA to the Future. AMS-DIMACS, vol.\u00a049, pp. 49\u201399. American Mathematical Society (1999)","key":"2_CR8","DOI":"10.1090\/dimacs\/049\/04"},{"doi-asserted-by":"crossref","unstructured":"Downey, R.G., Fellows, M.R.: Parameterized Complexity. Monographs in Computer Science. Springer, New York (1999)","key":"2_CR9","DOI":"10.1007\/978-1-4612-0515-9"},{"key":"2_CR10","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"276","DOI":"10.1007\/11847250_25","volume-title":"Parameterized and Exact Computation","author":"M.R. Fellows","year":"2006","unstructured":"Fellows, M.R.: The lost continent of polynomial time: Preprocessing and kernelization. In: Bodlaender, H.L., Langston, M.A. (eds.) IWPEC 2006. LNCS, vol.\u00a04169, pp. 276\u2013277. Springer, Heidelberg (2006)"},{"unstructured":"Flum, J., Grohe, M.: Parameterized Complexity Theory. Texts in Theoretical Computer Science. An EATCS Series, vol.\u00a0XIV. Springer (2006)","key":"2_CR11"},{"key":"2_CR12","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"107","DOI":"10.1007\/978-3-642-13182-0_10","volume-title":"Computer Science \u2013 Theory and Applications","author":"F.V. Fomin","year":"2010","unstructured":"Fomin, F.V.: Kernelization. In: Ablayev, F., Mayr, E.W. (eds.) CSR 2010. LNCS, vol.\u00a06072, pp. 107\u2013108. Springer, Heidelberg (2010)"},{"doi-asserted-by":"crossref","unstructured":"Ghallab, M., Nau, D.S., Traverso, P.: Automated planning - theory and practice. Elsevier (2004)","key":"2_CR13","DOI":"10.1016\/B978-155860856-6\/50021-1"},{"issue":"2","key":"2_CR14","doi-asserted-by":"publisher","first-page":"31","DOI":"10.1145\/1233481.1233493","volume":"38","author":"J. Guo","year":"2007","unstructured":"Guo, J., Niedermeier, R.: Invitation to data reduction and problem kernelization. ACM SIGACT News\u00a038(2), 31\u201345 (2007)","journal-title":"ACM SIGACT News"},{"issue":"2","key":"2_CR15","doi-asserted-by":"publisher","first-page":"583","DOI":"10.1137\/100794560","volume":"25","author":"J. Guo","year":"2011","unstructured":"Guo, J., Niedermeier, R., Such\u00fd, O.: Parameterized complexity of arc-weighted directed steiner problems. SIAM J. Discrete Math.\u00a025(2), 583\u2013599 (2011)","journal-title":"SIAM J. Discrete Math."},{"issue":"4","key":"2_CR16","doi-asserted-by":"publisher","first-page":"757","DOI":"10.1016\/S0022-0000(03)00078-3","volume":"67","author":"K. Pietrzak","year":"2003","unstructured":"Pietrzak, K.: On the parameterized complexity of the fixed alphabet shortest common supersequence and longest common subsequence problems. J. of Computer and System Sciences\u00a067(4), 757\u2013771 (2003)","journal-title":"J. of Computer and System Sciences"},{"issue":"3","key":"2_CR17","doi-asserted-by":"publisher","first-page":"287","DOI":"10.1016\/0304-3975(83)90020-8","volume":"26","author":"C.-K. Yap","year":"1983","unstructured":"Yap, C.-K.: Some consequences of nonuniform conditions on uniform classes. Theoretical Computer Science\u00a026(3), 287\u2013300 (1983)","journal-title":"Theoretical Computer Science"}],"container-title":["Lecture Notes in Computer Science","Algorithms and Complexity"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-38233-8_2","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,7,1]],"date-time":"2023-07-01T19:19:02Z","timestamp":1688239142000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-38233-8_2"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2013]]},"ISBN":["9783642382321","9783642382338"],"references-count":17,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-38233-8_2","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2013]]}}}