{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,24]],"date-time":"2026-03-24T06:24:59Z","timestamp":1774333499567,"version":"3.50.1"},"publisher-location":"Singapore","reference-count":29,"publisher":"Springer Nature Singapore","isbn-type":[{"value":"9789819571260","type":"print"},{"value":"9789819571277","type":"electronic"}],"license":[{"start":{"date-parts":[[2026,1,1]],"date-time":"2026-01-01T00:00:00Z","timestamp":1767225600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2026,1,1]],"date-time":"2026-01-01T00:00:00Z","timestamp":1767225600000},"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":[[2026]]},"DOI":"10.1007\/978-981-95-7127-7_18","type":"book-chapter","created":{"date-parts":[[2026,2,13]],"date-time":"2026-02-13T10:07:05Z","timestamp":1770977225000},"page":"263-275","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Space Efficient Algorithms for\u00a0Parameterised Problems"],"prefix":"10.1007","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-3653-6670","authenticated-orcid":false,"given":"Sheikh Shakil","family":"Akhtar","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-7086-5590","authenticated-orcid":false,"given":"Pranabendu","family":"Misra","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-0717-7303","authenticated-orcid":false,"given":"Geevarghese","family":"Philip","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2026,2,14]]},"reference":[{"key":"18_CR1","doi-asserted-by":"crossref","unstructured":"Agrawal, M., Kayal, N., Saxena, N.: Primes is in p. Ann. Math. 160(2), 781\u2013793 (2004). http:\/\/www.jstor.org\/stable\/3597229","DOI":"10.4007\/annals.2004.160.781"},{"key":"18_CR2","doi-asserted-by":"publisher","unstructured":"Alon, N., Dao, P., Hajirasouliha, I., Hormozdiari, F., Sahinalp, S.C.: Biomolecular network motif counting and discovery by color coding. Bioinformatics 24(13), i241\u2013i249 (2008). https:\/\/doi.org\/10.1093\/bioinformatics\/btn163","DOI":"10.1093\/bioinformatics\/btn163"},{"key":"18_CR3","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/978-3-642-11269-0_1","volume-title":"Parameterized and Exact Computation","author":"N Alon","year":"2009","unstructured":"Alon, N., Gutner, S.: Balanced hashing, color coding and approximate counting. In: Chen, J., Fomin, F.V. (eds.) IWPEC 2009. LNCS, vol. 5917, pp. 1\u201316. Springer, Heidelberg (2009). https:\/\/doi.org\/10.1007\/978-3-642-11269-0_1"},{"key":"18_CR4","doi-asserted-by":"publisher","unstructured":"Alon, N., Matias, Y., Szegedy, M.: The space complexity of approximating the frequency moments. In: Proceedings of the Twenty-Eighth Annual ACM Symposium on Theory of Computing, STOC \u201996, pp. 20\u201329. Association for Computing Machinery, New York (1996). https:\/\/doi.org\/10.1145\/237814.237823","DOI":"10.1145\/237814.237823"},{"key":"18_CR5","doi-asserted-by":"publisher","unstructured":"Alon, N., Yuster, R., Zwick, U.: Color-coding: a new method for finding simple paths, cycles and other small subgraphs within large graphs. In: Proceedings of the Twenty-Sixth Annual ACM Symposium on Theory of Computing, STOC \u201994, pp. 326\u2013335. Association for Computing Machinery, New York (1994). https:\/\/doi.org\/10.1145\/195058.195179","DOI":"10.1145\/195058.195179"},{"key":"18_CR6","doi-asserted-by":"crossref","unstructured":"Arora, S., Barak, B.: Computational Complexity: A Modern Approach. Cambridge University Press, Cambridge (2009)","DOI":"10.1017\/CBO9780511804090"},{"key":"18_CR7","doi-asserted-by":"crossref","unstructured":"Barman, S., Chawla, S.: Region growing for multi-route cuts. In: Proceedings of the Twenty-First Annual ACM-SIAM Symposium on Discrete Algorithms, SODA \u201910, pp. 404\u2013418. Society for Industrial and Applied Mathematics, USA (2010)","DOI":"10.1137\/1.9781611973075.34"},{"key":"18_CR8","doi-asserted-by":"publisher","unstructured":"Bergougnoux, B., et al.: Space-efficient parameterized algorithms on graphs of low shrubdepth. In: G\u00f8rtz, I.L., Farach-Colton, M., Puglisi, S.J., Herman, G. (eds.) 31st Annual European Symposium on Algorithms (ESA 2023). Leibniz International Proceedings in Informatics (LIPIcs), vol.\u00a0274, pp. 18:1\u201318:18. Schloss Dagstuhl \u2013 Leibniz-Zentrum f\u00fcr Informatik, Dagstuhl (2023). https:\/\/doi.org\/10.4230\/LIPIcs.ESA.2023.18. https:\/\/drops.dagstuhl.de\/entities\/document\/10.4230\/LIPIcs.ESA.2023.18","DOI":"10.4230\/LIPIcs.ESA.2023.18"},{"key":"18_CR9","doi-asserted-by":"publisher","unstructured":"Bodlaender, H.L., Groenland, C., Jacob, H.: List colouring trees in logarithmic space. In: Chechik, S., Navarro, G., Rotenberg, E., Herman, G. (eds.) 30th Annual European Symposium on Algorithms, ESA 2022, Berlin\/Potsdam, Germany, 5\u20139 September 2022. LIPIcs, vol.\u00a0244, pp. 24:1\u201324:15. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik (2022). https:\/\/doi.org\/10.4230\/LIPICS.ESA.2022.24, https:\/\/doi.org\/10.4230\/LIPIcs.ESA.2022.24","DOI":"10.4230\/LIPICS.ESA.2022.24"},{"key":"18_CR10","doi-asserted-by":"publisher","unstructured":"Bodlaender, H.L., Groenland, C., Jacob, H., Jaffke, L., Lima, P.T.: Xnlp-completeness for parameterized problems on graphs with a linear structure. In: Dell, H., Nederlof, J. (eds.) 17th International Symposium on Parameterized and Exact Computation, IPEC 2022, Potsdam, Germany, 7\u20139 September 2022. LIPIcs, vol.\u00a0249, pp. 8:1\u20138:18. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik (2022). https:\/\/doi.org\/10.4230\/LIPICS.IPEC.2022.8","DOI":"10.4230\/LIPICS.IPEC.2022.8"},{"key":"18_CR11","doi-asserted-by":"publisher","unstructured":"Bodlaender, H.L., Groenland, C., Nederlof, J., Swennenhuis, C.M.F.: Parameterized problems complete for nondeterministic FPT time and logarithmic space. In: 62nd IEEE Annual Symposium on Foundations of Computer Science, FOCS 2021, Denver, CO, USA, 7\u201310 February 2022, pp. 193\u2013204. IEEE (2021). https:\/\/doi.org\/10.1109\/FOCS52979.2021.00027","DOI":"10.1109\/FOCS52979.2021.00027"},{"key":"18_CR12","doi-asserted-by":"publisher","unstructured":"Bodlaender, H.L., Szil\u00e1gyi, K.: Xnlp-hardness of parameterized problems on planar graphs. In: Kr\u00e1l, D., Milanic, M. (eds.) Graph-Theoretic Concepts in Computer Science - 50th International Workshop, WG 2024, Gozd Martuljek, Slovenia, 19\u201321 June 2024, Revised Selected Papers. LNCS, vol. 14760, pp. 107\u2013120. Springer, Heidelberg (2024). https:\/\/doi.org\/10.1007\/978-3-031-75409-8_8","DOI":"10.1007\/978-3-031-75409-8_8"},{"key":"18_CR13","doi-asserted-by":"publisher","unstructured":"Carter, J., Wegman, M.N.: Universal classes of hash functions. J. Comput. Syst. Sci. 18(2), 143\u2013154 (1979). https:\/\/doi.org\/10.1016\/0022-0000(79)90044-8. https:\/\/www.sciencedirect.com\/science\/article\/pii\/0022000079900448","DOI":"10.1016\/0022-0000(79)90044-8"},{"key":"18_CR14","doi-asserted-by":"publisher","unstructured":"Chen, J., Chu, Z., Guo, Y., Yang, W.: Space limited graph algorithms on big data. In: Computing and Combinatorics: 28th International Conference, COCOON 2022, Shenzhen, China, 22\u201324 October 2022, Proceedings, pp. 255\u2013267. Springer, Heidelberg (2023). https:\/\/doi.org\/10.1007\/978-3-031-22105-7_23","DOI":"10.1007\/978-3-031-22105-7_23"},{"key":"18_CR15","doi-asserted-by":"publisher","unstructured":"Chen, J., Guo, Y., Huang, Q.: Linear-time parameterized algorithms with limited local resources. Inf. Comput. 289, 104951 (2022). https:\/\/doi.org\/10.1016\/j.ic.2022.104951. https:\/\/www.sciencedirect.com\/science\/article\/pii\/S0890540122001067","DOI":"10.1016\/j.ic.2022.104951"},{"key":"18_CR16","doi-asserted-by":"publisher","unstructured":"Chitnis, R., Cormode, G.: Towards a theory of parameterized streaming algorithms. In: Jansen, B.M.P., Telle, J.A. (eds.) 14th International Symposium on Parameterized and Exact Computation (IPEC 2019). Leibniz International Proceedings in Informatics (LIPIcs), vol.\u00a0148, pp. 7:1\u20137:15. Schloss Dagstuhl \u2013 Leibniz-Zentrum f\u00fcr Informatik, Dagstuhl (2019). https:\/\/doi.org\/10.4230\/LIPIcs.IPEC.2019.7. https:\/\/drops.dagstuhl.de\/entities\/document\/10.4230\/LIPIcs.IPEC.2019.7","DOI":"10.4230\/LIPIcs.IPEC.2019.7"},{"key":"18_CR17","volume-title":"Introduction to Algorithms","author":"TH Cormen","year":"2009","unstructured":"Cormen, T.H., Leiserson, C.E., Rivest, R.L., Stein, C.: Introduction to Algorithms, 3rd edn. The MIT Press, Cambridge (2009)","edition":"3"},{"key":"18_CR18","doi-asserted-by":"publisher","unstructured":"Cygan, M., ET AL.: Parameterized Algorithms. Springer, Heidelberg (2015). https:\/\/doi.org\/10.1007\/978-3-319-21275-3","DOI":"10.1007\/978-3-319-21275-3"},{"key":"18_CR19","doi-asserted-by":"publisher","unstructured":"Davidov, N., et al.: Maximum covering subtrees for phylogenetic networks. IEEE\/ACM Trans. Comput. Biol. Bioinf. 18(6), 2823\u20132827 (2020). https:\/\/doi.org\/10.1109\/TCBB.2020.3040910","DOI":"10.1109\/TCBB.2020.3040910"},{"issue":"3","key":"18_CR20","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":"18_CR21","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":"18_CR22","doi-asserted-by":"publisher","unstructured":"Feigenbaum, J., Kannan, S., McGregor, A., Suri, S., Zhang, J.: On graph problems in a semi-streaming model. Theor. Comput. Sci. 348(2), 207\u2013216 (2005). https:\/\/doi.org\/10.1016\/j.tcs.2005.09.013. https:\/\/www.sciencedirect.com\/science\/article\/pii\/S0304397505005323","DOI":"10.1016\/j.tcs.2005.09.013"},{"key":"18_CR23","doi-asserted-by":"publisher","unstructured":"Ghosh, P., Kuchlous, S.: New algorithms and lower bounds for streaming tournaments. In: Chan, T., Fischer, J., Iacono, J., Herman, G. (eds.) 32nd Annual European Symposium on Algorithms (ESA 2024). Leibniz International Proceedings in Informatics (LIPIcs), vol.\u00a0308, pp. 60:1\u201360:19. Schloss Dagstuhl \u2013 Leibniz-Zentrum f\u00fcr Informatik, Dagstuhl (2024). https:\/\/doi.org\/10.4230\/LIPIcs.ESA.2024.60. https:\/\/drops.dagstuhl.de\/entities\/document\/10.4230\/LIPIcs.ESA.2024.60","DOI":"10.4230\/LIPIcs.ESA.2024.60"},{"key":"18_CR24","doi-asserted-by":"crossref","unstructured":"Guo, J., Niedermeier, R.: Fixed-parameter tractability and data reduction for multicut in trees. Netw. Int. J. 46(3), 124\u2013135 (2005)","DOI":"10.1002\/net.20081"},{"key":"18_CR25","doi-asserted-by":"publisher","first-page":"260","DOI":"10.1007\/978-981-97-2340-9_22","volume-title":"Theory and Applications of Models of Computation","author":"F Kammer","year":"2024","unstructured":"Kammer, F., Sajenko, A.: Space-efficient graph kernelizations. In: Chen, X., Li, B. (eds.) Theory and Applications of Models of Computation, pp. 260\u2013271. Springer, Singapore (2024). https:\/\/doi.org\/10.1007\/978-981-97-2340-9_22"},{"key":"18_CR26","doi-asserted-by":"publisher","first-page":"882","DOI":"10.1007\/s00453-010-9454-5","volume":"61","author":"J Kneis","year":"2011","unstructured":"Kneis, J., Langer, A., Rossmanith, P.: A new algorithm for finding trees with many leaves. Algorithmica 61, 882\u2013897 (2011)","journal-title":"Algorithmica"},{"key":"18_CR27","doi-asserted-by":"publisher","unstructured":"Lokshtanov, D., Misra, P., Panolan, F., Ramanujan, M.S., Saurabh, S., Zehavi, M.: Meta-theorems for Parameterized Streaming Algorithms$$\\ddagger $$, pp. 712\u2013739 (2024). https:\/\/doi.org\/10.1137\/1.9781611977912.28. https:\/\/epubs.siam.org\/doi\/abs\/10.1137\/1.9781611977912.28","DOI":"10.1137\/1.9781611977912.28"},{"key":"18_CR28","doi-asserted-by":"publisher","unstructured":"McGregor, A.: Graph stream algorithms: a survey. SIGMOD Rec. 43(1), 9\u201320 (2014). https:\/\/doi.org\/10.1145\/2627692.2627694","DOI":"10.1145\/2627692.2627694"},{"key":"18_CR29","doi-asserted-by":"publisher","unstructured":"Reingold, O.: Undirected st-connectivity in log-space. In: Proceedings of the Thirty-Seventh Annual ACM Symposium on Theory of Computing, STOC \u201905, pp. 376\u2013385. Association for Computing Machinery, New York (2005). https:\/\/doi.org\/10.1145\/1060590.1060647","DOI":"10.1145\/1060590.1060647"}],"container-title":["Lecture Notes in Computer Science","WALCOM: Algorithms and Computation"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-981-95-7127-7_18","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,3,24]],"date-time":"2026-03-24T04:05:08Z","timestamp":1774325108000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-981-95-7127-7_18"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2026]]},"ISBN":["9789819571260","9789819571277"],"references-count":29,"URL":"https:\/\/doi.org\/10.1007\/978-981-95-7127-7_18","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2026]]},"assertion":[{"value":"14 February 2026","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"WALCOM","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"International Conference and Workshops on Algorithms and Computation","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Perugia","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Italy","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2026","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"4 March 2026","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"6 March 2026","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"20","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"walcom2026","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"https:\/\/mozart.diei.unipg.it\/walcom2026","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}}]}}