{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,14]],"date-time":"2026-02-14T02:32:43Z","timestamp":1771036363469,"version":"3.50.1"},"publisher-location":"Singapore","reference-count":19,"publisher":"Springer Nature Singapore","isbn-type":[{"value":"9789819723393","type":"print"},{"value":"9789819723409","type":"electronic"}],"license":[{"start":{"date-parts":[[2024,1,1]],"date-time":"2024-01-01T00:00:00Z","timestamp":1704067200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2024,1,1]],"date-time":"2024-01-01T00:00:00Z","timestamp":1704067200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2024]]},"DOI":"10.1007\/978-981-97-2340-9_22","type":"book-chapter","created":{"date-parts":[[2024,5,2]],"date-time":"2024-05-02T23:01:51Z","timestamp":1714690911000},"page":"260-271","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":2,"title":["Space-Efficient Graph Kernelizations"],"prefix":"10.1007","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-2662-3471","authenticated-orcid":false,"given":"Frank","family":"Kammer","sequence":"first","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0001-5946-8087","authenticated-orcid":false,"given":"Andrej","family":"Sajenko","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2024,5,3]]},"reference":[{"key":"22_CR1","doi-asserted-by":"publisher","unstructured":"Bannach, M., Stockhusen, C., Tantau, T.: Fast parallel fixed-parameter algorithms via color coding. In: Proceedings of the 10th International Symposium on Parameterized and Exact Computation (IPEC 2015). LIPIcs, vol.\u00a043, pp. 224\u2013235. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik (2015). https:\/\/doi.org\/10.4230\/LIPIcs.IPEC.2015.224","DOI":"10.4230\/LIPIcs.IPEC.2015.224"},{"key":"22_CR2","doi-asserted-by":"crossref","unstructured":"Becker, A., Geiger, D.: Approximation algorithms for the loop cutset problem. In: Proceedings of the 10th Annual Conference on Uncertainty in Artificial Intelligence (UAI 1994), pp. 60\u201368. Morgan Kaufmann (1994)","DOI":"10.1016\/B978-1-55860-332-5.50013-4"},{"key":"22_CR3","unstructured":"Biswas, A., Raman, V., Satti, S.R., Saurabh, S.: Space-efficient FPT algorithms. CoRR, abs\/2112.15233 (2021). arXiv:2112.15233"},{"issue":"1","key":"22_CR4","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. Ann. Pure Appl. Log. 84(1), 119\u2013138 (1997). https:\/\/doi.org\/10.1016\/S0168-0072(95)00020-8","journal-title":"Ann. Pure Appl. Log."},{"key":"22_CR5","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"126","DOI":"10.1007\/978-3-030-48966-3_10","volume-title":"Combinatorial Algorithms","author":"S Chakraborty","year":"2020","unstructured":"Chakraborty, S., Sadakane, K., Satti, S.R.: Optimal in-place algorithms for basic graph problems. In: G\u0105sieniec, L., Klasing, R., Radzik, T. (eds.) IWOCA 2020. LNCS, vol. 12126, pp. 126\u2013139. Springer, Cham (2020). https:\/\/doi.org\/10.1007\/978-3-030-48966-3_10"},{"issue":"7","key":"22_CR6","doi-asserted-by":"publisher","first-page":"1188","DOI":"10.1016\/j.jcss.2008.05.002","volume":"74","author":"J Chen","year":"2008","unstructured":"Chen, J., Fomin, F.V., Liu, Y., Songjian, L., Villanger, Y.: Improved algorithms for feedback vertex set problems. J. Comput. Syst. Sci. 74(7), 1188\u20131198 (2008). https:\/\/doi.org\/10.1016\/j.jcss.2008.05.002","journal-title":"J. Comput. Syst. Sci."},{"issue":"3","key":"22_CR7","doi-asserted-by":"publisher","first-page":"385","DOI":"10.1016\/0196-6774(87)90018-6","volume":"8","author":"SA Cook","year":"1987","unstructured":"Cook, S.A., McKenzie, P.: Problems complete for deterministic logarithmic space. J. Algorithms 8(3), 385\u2013394 (1987). https:\/\/doi.org\/10.1016\/0196-6774(87)90018-6","journal-title":"J. Algorithms"},{"key":"22_CR8","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-21275-3","volume-title":"Parameterized Algorithms","author":"M Cygan","year":"2015","unstructured":"Cygan, M., et al.: Parameterized Algorithms. Springer, Cham (2015). https:\/\/doi.org\/10.1007\/978-3-319-21275-3"},{"issue":"3","key":"22_CR9","doi-asserted-by":"publisher","first-page":"337","DOI":"10.1016\/j.tcs.2005.10.004","volume":"351","author":"P Damaschke","year":"2006","unstructured":"Damaschke, P.: Parameterized enumeration, transversals, and imperfect phylogeny reconstruction. Theor. Comput. Sci. 351(3), 337\u2013350 (2006). https:\/\/doi.org\/10.1016\/j.tcs.2005.10.004","journal-title":"Theor. Comput. Sci."},{"key":"22_CR10","doi-asserted-by":"publisher","unstructured":"Datta, S., Kulkarni, R., Mukherjee, A.: Space-efficient approximation scheme for maximum matching in sparse graphs. In: Proceedings of the 41st International Symposium on Mathematical Foundations of Computer Science (MFCS 2016). LIPIcs, vol.\u00a058, pp. 28:1\u201328:12. Schloss Dagstuhl \u2013 Leibniz-Zentrum f\u00fcr Informatik (2016). https:\/\/doi.org\/10.4230\/LIPIcs.MFCS.2016.28","DOI":"10.4230\/LIPIcs.MFCS.2016.28"},{"key":"22_CR11","series-title":"Monographs in Computer Science","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4612-0515-9","volume-title":"Parameterized Complexity","author":"RG Downey","year":"1999","unstructured":"Downey, R.G., Fellows, M.R.: Parameterized Complexity. Monographs in Computer Science, Springer, Cham (1999). https:\/\/doi.org\/10.1007\/978-1-4612-0515-9"},{"issue":"3","key":"22_CR12","doi-asserted-by":"publisher","first-page":"661","DOI":"10.1007\/s00453-014-9944-y","volume":"71","author":"M Elberfeld","year":"2015","unstructured":"Elberfeld, M., Stockhusen, C., Tantau, T.: On the space and circuit complexity of parameterized problems: classes and completeness. Algorithmica 71(3), 661\u2013701 (2015). https:\/\/doi.org\/10.1007\/s00453-014-9944-y","journal-title":"Algorithmica"},{"key":"22_CR13","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"299","DOI":"10.1007\/978-3-662-48054-0_25","volume-title":"Mathematical Foundations of Computer Science 2015","author":"S Fafianie","year":"2015","unstructured":"Fafianie, S., Kratsch, S.: A shortcut to (sun)flowers: kernels in logarithmic space or linear time. In: Italiano, G.F., Pighizzini, G., Sannella, D.T. (eds.) MFCS 2015. LNCS, vol. 9235, pp. 299\u2013310. Springer, Heidelberg (2015). https:\/\/doi.org\/10.1007\/978-3-662-48054-0_25"},{"key":"22_CR14","doi-asserted-by":"publisher","first-page":"46","DOI":"10.1016\/j.tcs.2021.04.002","volume":"868","author":"K Heeger","year":"2021","unstructured":"Heeger, K., Himmel, A.-S., Kammer, F., Niedermeier, R., Renken, M., Sajenko, A.: Multistage graph problems on a global budget. Theor. Comput. Sci. 868, 46\u201364 (2021). https:\/\/doi.org\/10.1016\/j.tcs.2021.04.002","journal-title":"Theor. Comput. Sci."},{"key":"22_CR15","doi-asserted-by":"publisher","unstructured":"Iwata, Y.: Linear-time kernelization for feedback vertex set. In: Proceedings of the 44th International Colloquium on Automata, Languages, and Programming, (ICALP 2017). LIPIcs, vol.\u00a080, pp. 68:1\u201368:14. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik (2017). https:\/\/doi.org\/10.4230\/LIPIcs.ICALP.2017.68","DOI":"10.4230\/LIPIcs.ICALP.2017.68"},{"key":"22_CR16","doi-asserted-by":"publisher","unstructured":"Izumi, T., Otachi, Y.: Sublinear-space lexicographic depth-first search for bounded treewidth graphs and planar graphs. In: Proceedings of the 47th International Colloquium on Automata, Languages, and Programming, (ICALP 2020). LIPIcs, vol. 168, pp. 67:1\u201367:17. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik (2020). https:\/\/doi.org\/10.4230\/LIPICS.ICALP.2020.67","DOI":"10.4230\/LIPICS.ICALP.2020.67"},{"key":"22_CR17","unstructured":"Kammer, F., Sajenko, A.: Space-efficient graph kernelizations. CoRR, abs\/2007.11643 (2020). arXiv:2007.11643"},{"key":"22_CR18","doi-asserted-by":"publisher","first-page":"20","DOI":"10.1016\/j.tcs.2016.06.012","volume":"657","author":"W Li","year":"2017","unstructured":"Li, W., Feng, Q., Chen, J., Shuai, H.: Improved kernel results for some FPT problems based on simple observations. Theor. Comput. Sci. 657, 20\u201327 (2017). https:\/\/doi.org\/10.1016\/j.tcs.2016.06.012","journal-title":"Theor. Comput. Sci."},{"key":"22_CR19","doi-asserted-by":"publisher","unstructured":"Thomass\u00e9, S.: A 4k$${}^{\\text{2}}$$ kernel for feedback vertex set. ACM Trans. Algorithms, 6(2), 32:1\u201332:8 (2010). https:\/\/doi.org\/10.1145\/1721837.1721848","DOI":"10.1145\/1721837.1721848"}],"container-title":["Lecture Notes in Computer Science","Theory and Applications of Models of Computation"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-981-97-2340-9_22","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,5,2]],"date-time":"2024-05-02T23:03:45Z","timestamp":1714691025000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-981-97-2340-9_22"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024]]},"ISBN":["9789819723393","9789819723409"],"references-count":19,"URL":"https:\/\/doi.org\/10.1007\/978-981-97-2340-9_22","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2024]]},"assertion":[{"value":"3 May 2024","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"TAMC","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Annual Conference on Theory and Applications of Models of Computation","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Hong Kong","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"China","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2024","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"13 May 2024","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"15 May 2024","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"tamc2024","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"https:\/\/tamc2024.comp.polyu.edu.hk\/","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}}]}}