{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,27]],"date-time":"2025-03-27T21:03:25Z","timestamp":1743109405664,"version":"3.40.3"},"publisher-location":"Singapore","reference-count":14,"publisher":"Springer Nature Singapore","isbn-type":[{"type":"print","value":"9789819778003"},{"type":"electronic","value":"9789819778010"}],"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-7801-0_18","type":"book-chapter","created":{"date-parts":[[2024,9,19]],"date-time":"2024-09-19T18:05:37Z","timestamp":1726769137000},"page":"209-219","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["On the\u00a0Existence of\u00a0Parameterized Algorithms for\u00a0the\u00a0Shortest Common Supersequence and\u00a0Related Problems"],"prefix":"10.1007","author":[{"given":"Muzhou","family":"Chen","sequence":"first","affiliation":[]},{"given":"Haitao","family":"Jiang","sequence":"additional","affiliation":[]},{"given":"Nan","family":"Liu","sequence":"additional","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0002-4344-8791","authenticated-orcid":false,"given":"Lusheng","family":"Wang","sequence":"additional","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0002-3929-4128","authenticated-orcid":false,"given":"Binhai","family":"Zhu","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2024,9,19]]},"reference":[{"key":"18_CR1","doi-asserted-by":"publisher","first-page":"11","DOI":"10.1016\/j.jda.2013.03.004","volume":"21","author":"R Dondi","year":"2013","unstructured":"Dondi, R.: The constrained shortest common supersequence problem. J. Discrete Algorithms 21, 11\u201317 (2013)","journal-title":"J. Discrete Algorithms"},{"key":"18_CR2","volume-title":"Parameterized Complexity","author":"R Downey","year":"2012","unstructured":"Downey, R., Fellows, M.: Parameterized Complexity. Springer, New York (2012)"},{"issue":"1\u20132","key":"18_CR3","doi-asserted-by":"publisher","first-page":"109","DOI":"10.1016\/0304-3975(94)00097-3","volume":"141","author":"RG Downey","year":"1995","unstructured":"Downey, R.G., Fellows, M.R.: Fixed-parameter tractability and completeness II: on completeness for W[1]. Theoret. Comput. Sci. 141(1\u20132), 109\u2013131 (1995)","journal-title":"Theoret. Comput. Sci."},{"key":"18_CR4","series-title":"Texts in Theoretical Computer Science. An EATCS Series","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-29953-X","volume-title":"Parameterized Complexity Theory","author":"J Flum","year":"2006","unstructured":"Flum, J., Grohe, M.: Parameterized Complexity Theory. Texts in Theoretical Computer Science. An EATCS Series, Springer, Heidelberg (2006). https:\/\/doi.org\/10.1007\/3-540-29953-X"},{"issue":"5","key":"18_CR5","doi-asserted-by":"publisher","first-page":"1122","DOI":"10.1137\/S009753979223842X","volume":"24","author":"T Jiang","year":"1995","unstructured":"Jiang, T., Li, M.: On the approximation of shortest common supersequences and longest common subsequences. SIAM J. Comput. 24(5), 1122\u20131139 (1995)","journal-title":"SIAM J. Comput."},{"key":"18_CR6","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"93","DOI":"10.1007\/978-3-540-30213-1_13","volume-title":"String Processing and Information Retrieval","author":"A Kosowski","year":"2004","unstructured":"Kosowski, A.: An efficient algorithm for the longest tandem scattered subsequence problem. In: Apostolico, A., Melucci, M. (eds.) SPIRE 2004. LNCS, vol. 3246, pp. 93\u2013100. Springer, Heidelberg (2004). https:\/\/doi.org\/10.1007\/978-3-540-30213-1_13"},{"key":"18_CR7","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"446","DOI":"10.1007\/978-3-031-49611-0_32","volume-title":"COCOA 2023, Part I","author":"M Lafond","year":"2023","unstructured":"Lafond, M., Lai, W., Liyanage, A., Zhu, B.: The longest subsequence-repeated subsequence problem. In: Weili, W., Guo, J. (eds.) COCOA 2023, Part I. LNCS, vol. 14461, pp. 446\u2013458. Springer, Cham (2023). https:\/\/doi.org\/10.1007\/978-3-031-49611-0_32"},{"key":"18_CR8","unstructured":"Lafond, M., Zhu, B., Zou, P.: Genomic problems involving copy number profiles: complexity and algorithms. In: G\u00f8rtz, I.L., Weimann, O. (eds.) 31st Annual Symposium on Combinatorial Pattern Matching, CPM 2020, Copenhagen, Denmark, 17\u201319 June 2020. LIPIcs, vol. 161, pp. 22:1\u201322:15. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik (2020)"},{"issue":"2","key":"18_CR9","doi-asserted-by":"publisher","first-page":"322","DOI":"10.1145\/322063.322075","volume":"25","author":"D Maier","year":"1978","unstructured":"Maier, D.: The complexity of some problems on subsequences and supersequences. J. ACM 25(2), 322\u2013336 (1978)","journal-title":"J. ACM"},{"key":"18_CR10","doi-asserted-by":"publisher","DOI":"10.1093\/acprof:oso\/9780198566076.001.0001","volume-title":"Invitation to Fixed-Parameter Algorithms","author":"R Niedermeier","year":"2006","unstructured":"Niedermeier, R.: Invitation to Fixed-Parameter Algorithms. Oxford University Press, Oxford (2006)"},{"issue":"4","key":"18_CR11","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. Comput. Syst. Sci. 67(4), 757\u2013771 (2003)","journal-title":"J. Comput. Syst. Sci."},{"key":"18_CR12","first-page":"1","volume":"5","author":"VG Timkovskii","year":"1989","unstructured":"Timkovskii, V.G.: Complexity of common subsequences and supersequences problems and related problems. Kibernetika 5, 1\u201313 (1989)","journal-title":"Kibernetika"},{"key":"18_CR13","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"367","DOI":"10.1007\/978-3-031-43980-3_30","volume-title":"SPIRE 2023","author":"L Wang","year":"2023","unstructured":"Wang, L., Zhu, B.: Algorithms and hardness for the longest common subsequence of three strings and related problems. In: Nardini, F.M., Pisanti, N., Venturini, R. (eds.) SPIRE 2023. LNCS, vol. 14240, pp. 367\u2013380. Springer, Cham (2023). https:\/\/doi.org\/10.1007\/978-3-031-43980-3_30"},{"issue":"10","key":"18_CR14","doi-asserted-by":"publisher","first-page":"1343","DOI":"10.1089\/cmb.2007.0156","volume":"14","author":"B Zhu","year":"2007","unstructured":"Zhu, B.: Protein local structure alignment under the discrete Fr\u00e9chet distance. J. Comput. Biol. 14(10), 1343\u20131351 (2007)","journal-title":"J. Comput. Biol."}],"container-title":["Lecture Notes in Computer Science","Algorithmic Aspects in Information and Management"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-981-97-7801-0_18","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,9,19]],"date-time":"2024-09-19T18:08:51Z","timestamp":1726769331000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-981-97-7801-0_18"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024]]},"ISBN":["9789819778003","9789819778010"],"references-count":14,"URL":"https:\/\/doi.org\/10.1007\/978-981-97-7801-0_18","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2024]]},"assertion":[{"value":"19 September 2024","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"AAIM","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"International Conference on Algorithmic Aspects in Information and Management","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Dallas, TX","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"USA","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":"21 September 2024","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"23 September 2024","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"18","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"aaim2024","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"https:\/\/theory.utdallas.edu\/AAIM2024\/index.html","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}}]}}