{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,4,7]],"date-time":"2025-04-07T13:10:08Z","timestamp":1744031408335,"version":"3.40.3"},"publisher-location":"Berlin, Heidelberg","reference-count":16,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642332920"},{"type":"electronic","value":"9783642332937"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2012]]},"DOI":"10.1007\/978-3-642-33293-7_20","type":"book-chapter","created":{"date-parts":[[2012,8,29]],"date-time":"2012-08-29T10:50:58Z","timestamp":1346237458000},"page":"206-217","source":"Crossref","is-referenced-by-count":9,"title":["On the Space Complexity of Parameterized Problems"],"prefix":"10.1007","author":[{"given":"Michael","family":"Elberfeld","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Christoph","family":"Stockhusen","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Till","family":"Tantau","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"issue":"3","key":"20_CR1","doi-asserted-by":"publisher","first-page":"235","DOI":"10.1016\/0168-0072(94)00034-Z","volume":"73","author":"K.A. Abrahamson","year":"1995","unstructured":"Abrahamson, K.A., Downey, R.G., Fellows, M.R.: Fixed-parameter tractability and completeness IV: On completeness for W[P] and PSPACE analogues. Annals of Pure and Applied Logic\u00a073(3), 235\u2013276 (1995)","journal-title":"Annals of Pure and Applied Logic"},{"issue":"1","key":"20_CR2","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1006\/jagm.1993.1001","volume":"14","author":"H.L. Bodlaender","year":"1993","unstructured":"Bodlaender, H.L.: On linear time minor tests with depth-first search. Journal of Algorithms\u00a014(1), 1\u201323 (1993)","journal-title":"Journal of Algorithms"},{"issue":"6","key":"20_CR3","doi-asserted-by":"publisher","first-page":"1305","DOI":"10.1137\/S0097539793251219","volume":"25","author":"H.L. Bodlaender","year":"1996","unstructured":"Bodlaender, H.L.: A linear time algorithm for finding tree-decompositions of small treewidth. Siam Journal on Computing\u00a025(6), 1305\u20131317 (1996)","journal-title":"Siam Journal on Computing"},{"issue":"1","key":"20_CR4","doi-asserted-by":"publisher","first-page":"31","DOI":"10.1016\/0304-3975(94)00251-D","volume":"147","author":"H.L. Bodlaender","year":"1995","unstructured":"Bodlaender, H.L., Downey, R.D., Fellows, M.R., Wareham, H.T.: The parameterized complexity of sequence alignment and consensus. Theoretical Computer Science\u00a0147(1), 31\u201354 (1995)","journal-title":"Theoretical Computer Science"},{"issue":"1","key":"20_CR5","doi-asserted-by":"publisher","first-page":"119","DOI":"10.1016\/S0168-0072(95)00020-8","volume":"84","author":"L. Cai","year":"1997","unstructured":"Cai, L., Chen, J., Downey, R.G., Fellows, M.R.: Advice classes of parameterized tractability. Annals of Pure and Applied Logic\u00a084(1), 119\u2013138 (1997); Asian Logic Conference","journal-title":"Annals of Pure and Applied Logic"},{"issue":"5","key":"20_CR6","doi-asserted-by":"publisher","first-page":"2","DOI":"10.1145\/1411509.1411511","volume":"55","author":"J. Chen","year":"2008","unstructured":"Chen, J., Liu, Y., Lu, S., O\u2019Sullivan, B., Razgon, I.: A fixed-parameter algorithm for the directed feedback vertex set problem. Journal of the ACM\u00a055(5), 21:2\u201321:19 (2008)","journal-title":"Journal of the ACM"},{"key":"20_CR7","doi-asserted-by":"crossref","unstructured":"Chen, Y., Flum, J., Grohe, M.: Bounded nondeterminism and alternation in parameterized complexity theory. In: CCC 2003, pp. 13\u201329 (2003)","DOI":"10.1109\/CCC.2003.1214407"},{"issue":"3","key":"20_CR8","doi-asserted-by":"publisher","first-page":"385","DOI":"10.1016\/0196-6774(87)90018-6","volume":"8","author":"S.A. Cook","year":"1987","unstructured":"Cook, S.A., McKenzie, P.: Problems complete for deterministic logarithmic space. Journal of Algorithms\u00a08(3), 385\u2013394 (1987)","journal-title":"Journal of Algorithms"},{"key":"20_CR9","doi-asserted-by":"crossref","unstructured":"Downey, R.G., Fellows, M.R.: Parameterized Complexity. Springer (1999)","DOI":"10.1007\/978-1-4612-0515-9"},{"key":"20_CR10","doi-asserted-by":"crossref","unstructured":"Elberfeld, M., Jakoby, A., Tantau, T.: Logspace versions of the theorems of Bodlaender and Courcelle. In: FOCS 2012, pp. 143\u2013152 (2010)","DOI":"10.1109\/FOCS.2010.21"},{"key":"20_CR11","doi-asserted-by":"publisher","first-page":"291","DOI":"10.1016\/S0890-5401(03)00161-5","volume":"187","author":"J. Flum","year":"2003","unstructured":"Flum, J., Grohe, M.: Describing parameterized complexity classes. Information and Computation\u00a0187, 291\u2013319 (2003)","journal-title":"Information and Computation"},{"key":"20_CR12","unstructured":"Flum, J., Grohe, M.: Parameterized Complexity Theory. Springer (2006)"},{"key":"20_CR13","doi-asserted-by":"publisher","first-page":"336","DOI":"10.1007\/BF00289513","volume":"1","author":"J. Hartmanis","year":"1972","unstructured":"Hartmanis, J.: On non-determinancy in simple computing devices. Acta Informatica\u00a01, 336\u2013344 (1972)","journal-title":"Acta Informatica"},{"issue":"1","key":"20_CR14","doi-asserted-by":"publisher","first-page":"68","DOI":"10.1016\/S0022-0000(75)80050-X","volume":"11","author":"N.D. Jones","year":"1975","unstructured":"Jones, N.D.: Space-bounded reducibility among combinatorial problems. Journal of Computer and System Sciences\u00a011(1), 68\u201385 (1975)","journal-title":"Journal of Computer and System Sciences"},{"issue":"1","key":"20_CR15","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/BF01683259","volume":"10","author":"N.D. Jones","year":"1976","unstructured":"Jones, N.D., Edmund Lien, Y., Laaser, W.T.: New problems complete for nondeterministic log space. Mathematical Systems Theory\u00a010(1), 1\u201317 (1976)","journal-title":"Mathematical Systems Theory"},{"issue":"4","key":"20_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. Journal of Computer and System Science\u00a067(4), 757\u2013771 (2003)","journal-title":"Journal of Computer and System Science"}],"container-title":["Lecture Notes in Computer Science","Parameterized and Exact Computation"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-33293-7_20.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,4,7]],"date-time":"2025-04-07T12:38:10Z","timestamp":1744029490000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-33293-7_20"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2012]]},"ISBN":["9783642332920","9783642332937"],"references-count":16,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-33293-7_20","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2012]]}}}