{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,12,3]],"date-time":"2025-12-03T18:07:44Z","timestamp":1764785264962,"version":"3.40.3"},"publisher-location":"Cham","reference-count":35,"publisher":"Springer Nature Switzerland","isbn-type":[{"type":"print","value":"9783031491894"},{"type":"electronic","value":"9783031491900"}],"license":[{"start":{"date-parts":[[2023,12,9]],"date-time":"2023-12-09T00:00:00Z","timestamp":1702080000000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2023,12,9]],"date-time":"2023-12-09T00:00:00Z","timestamp":1702080000000},"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-3-031-49190-0_9","type":"book-chapter","created":{"date-parts":[[2023,12,8]],"date-time":"2023-12-08T09:02:36Z","timestamp":1702026156000},"page":"127-140","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":3,"title":["Polynomial Turing Compressions for\u00a0Some Graph Problems Parameterized by\u00a0Modular-Width"],"prefix":"10.1007","author":[{"ORCID":"https:\/\/orcid.org\/0009-0003-5300-606X","authenticated-orcid":false,"given":"Weidong","family":"Luo","sequence":"first","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2023,12,9]]},"reference":[{"key":"9_CR1","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"14","DOI":"10.1007\/978-3-642-17493-3_4","volume-title":"Parameterized and Exact Computation","author":"AM Ambalath","year":"2010","unstructured":"Ambalath, A.M., et al.: On the kernelization complexity of colorful motifs. In: Raman, V., Saurabh, S. (eds.) IPEC 2010. LNCS, vol. 6478, pp. 14\u201325. Springer, Heidelberg (2010). https:\/\/doi.org\/10.1007\/978-3-642-17493-3_4"},{"issue":"9","key":"9_CR2","doi-asserted-by":"publisher","first-page":"2586","DOI":"10.1007\/s00453-020-00700-y","volume":"82","author":"R Belmonte","year":"2020","unstructured":"Belmonte, R., Hanaka, T., Lampis, M., Ono, H., Otachi, Y.: Independent set reconfiguration parameterized by modular-width. Algorithmica 82(9), 2586\u20132605 (2020)","journal-title":"Algorithmica"},{"key":"9_CR3","doi-asserted-by":"publisher","first-page":"30","DOI":"10.1016\/j.tcs.2019.02.030","volume":"782","author":"B Bergougnoux","year":"2019","unstructured":"Bergougnoux, B., Kant\u00e9, M.M.: Fast exact algorithms for some connectivity problems parameterized by clique-width. Theor. Comput. Sci. 782, 30\u201353 (2019)","journal-title":"Theor. Comput. Sci."},{"key":"9_CR4","unstructured":"Bodlaender, H.L., et al.: Open problems in parameterized and exact computation. In: IWPEC 2008 (2008)"},{"key":"9_CR5","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"563","DOI":"10.1007\/978-3-540-70575-8_46","volume-title":"Automata, Languages and Programming","author":"HL Bodlaender","year":"2008","unstructured":"Bodlaender, H.L., Downey, R.G., Fellows, M.R., Hermelin, D.: On problems without polynomial kernels (extended abstract). In: Aceto, L., Damg\u00e5rd, I., Goldberg, L.A., Halld\u00f3rsson, M.M., Ing\u00f3lfsd\u00f3ttir, A., Walukiewicz, I. (eds.) ICALP 2008. LNCS, vol. 5125, pp. 563\u2013574. Springer, Heidelberg (2008). https:\/\/doi.org\/10.1007\/978-3-540-70575-8_46"},{"issue":"1","key":"9_CR6","doi-asserted-by":"publisher","first-page":"277","DOI":"10.1137\/120880240","volume":"28","author":"HL Bodlaender","year":"2014","unstructured":"Bodlaender, H.L., Jansen, B.M.P., Kratsch, S.: Kernelization lower bounds by cross-composition. SIAM J. Discret. Math. 28(1), 277\u2013305 (2014)","journal-title":"SIAM J. Discret. Math."},{"key":"9_CR7","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"174","DOI":"10.1007\/978-3-642-15155-2_17","volume-title":"Mathematical Foundations of Computer Science 2010","author":"HL Bodlaender","year":"2010","unstructured":"Bodlaender, H.L., van Leeuwen, E.J., van Rooij, J.M.M., Vatshelle, M.: Faster algorithms on branch and clique decompositions. In: Hlin\u011bn\u00fd, P., Ku\u010dera, A. (eds.) MFCS 2010. LNCS, vol. 6281, pp. 174\u2013185. Springer, Heidelberg (2010). https:\/\/doi.org\/10.1007\/978-3-642-15155-2_17"},{"key":"9_CR8","unstructured":"Burjons, E., Rossmanith, P.: Lower bounds for conjunctive and disjunctive turing kernels. In: IPEC 2021. Schloss Dagstuhl-Leibniz-Zentrum f\u00fcr Informatik (2021)"},{"issue":"2","key":"9_CR9","doi-asserted-by":"publisher","first-page":"125","DOI":"10.1007\/s002249910009","volume":"33","author":"B Courcelle","year":"2000","unstructured":"Courcelle, B., Makowsky, J.A., Rotics, U.: Linear time solvable optimization problems on graphs of bounded clique-width. Theory Comput. Syst. 33(2), 125\u2013150 (2000)","journal-title":"Theory Comput. Syst."},{"issue":"1\u20133","key":"9_CR10","doi-asserted-by":"publisher","first-page":"77","DOI":"10.1016\/S0166-218X(99)00184-5","volume":"101","author":"B Courcelle","year":"2000","unstructured":"Courcelle, B., Olariu, S.: Upper bounds to the clique width of graphs. Discret. Appl. Math. 101(1\u20133), 77\u2013114 (2000)","journal-title":"Discret. Appl. Math."},{"key":"9_CR11","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"},{"key":"9_CR12","doi-asserted-by":"publisher","first-page":"164","DOI":"10.1016\/j.jcss.2021.02.005","volume":"119","author":"H Donkers","year":"2021","unstructured":"Donkers, H., Jansen, B.M.P.: A Turing kernelization dichotomy for structural parameterizations of f-minor-free deletion. J. Comput. Syst. Sci. 119, 164\u2013182 (2021)","journal-title":"J. Comput. Syst. Sci."},{"key":"9_CR13","series-title":"Texts in Computer Science","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4471-5559-1","volume-title":"Fundamentals of Parameterized Complexity","author":"RG Downey","year":"2013","unstructured":"Downey, R.G., Fellows, M.R.: Fundamentals of Parameterized Complexity. TCS, Springer, London (2013). https:\/\/doi.org\/10.1007\/978-1-4471-5559-1"},{"key":"9_CR14","unstructured":"Fernau, H., Fomin, F.V., Lokshtanov, D., Raible, D., Saurabh, S., Villanger, Y.: Kernel(s) for problems with no kernel: on out-trees with many leaves. In: STACS 2009, February 26\u201328, Freiburg, Germany, Proceedings. LIPIcs, vol. 3, pp. 421\u2013432 (2009)"},{"key":"9_CR15","unstructured":"Fluschnik, T., Heeger, K., Hermelin, D.: Polynomial Turing kernels for clique with an optimal number of queries. CoRR abs\/2110.03279 (2021)"},{"issue":"4","key":"9_CR16","doi-asserted-by":"publisher","first-page":"1146","DOI":"10.1007\/s00453-017-0297-1","volume":"80","author":"FV Fomin","year":"2017","unstructured":"Fomin, F.V., Liedloff, M., Montealegre, P., Todinca, I.: Algorithms parameterized by vertex cover and modular width, through potential maximal cliques. Algorithmica 80(4), 1146\u20131169 (2017)","journal-title":"Algorithmica"},{"key":"9_CR17","unstructured":"Fomin, F.V., Lokshtanov, D., Saurabh, S., Zehavi, M.: Kernelization: Theory of Parameterized Preprocessing. Cambridge University Press, Cambridge (2013)"},{"key":"9_CR18","doi-asserted-by":"crossref","unstructured":"Fortnow, L., Santhanam, R.: Infeasibility of instance compression and succinct PCPS for NP. In: STOC 2008, Victoria, British Columbia, Canada, May 17\u201320, pp. 133\u2013142. ACM (2008)","DOI":"10.1145\/1374376.1374398"},{"key":"9_CR19","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"163","DOI":"10.1007\/978-3-319-03898-8_15","volume-title":"Parameterized and Exact Computation","author":"J Gajarsk\u00fd","year":"2013","unstructured":"Gajarsk\u00fd, J., Lampis, M., Ordyniak, S.: Parameterized algorithms for modular-width. In: Gutin, G., Szeider, S. (eds.) IPEC 2013. LNCS, vol. 8246, pp. 163\u2013176. Springer, Cham (2013). https:\/\/doi.org\/10.1007\/978-3-319-03898-8_15"},{"issue":"1","key":"9_CR20","doi-asserted-by":"publisher","first-page":"41","DOI":"10.1016\/j.cosrev.2010.01.001","volume":"4","author":"M Habib","year":"2010","unstructured":"Habib, M., Paul, C.: A survey of the algorithmic aspects of modular decomposition. Comput. Sci. Rev. 4(1), 41\u201359 (2010)","journal-title":"Comput. Sci. Rev."},{"key":"9_CR21","unstructured":"Hegerfeld, F., Kratsch, S.: Towards exact structural thresholds for parameterized complexity. In: IPEC 2022, September 7\u20139, 2022, Potsdam, Germany. LIPIcs, vol. 249, pp. 17:1\u201317:20. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik (2022)"},{"issue":"3","key":"9_CR22","doi-asserted-by":"publisher","first-page":"702","DOI":"10.1007\/s00453-014-9910-8","volume":"71","author":"D Hermelin","year":"2015","unstructured":"Hermelin, D., Kratsch, S., Soltys, K., Wahlstr\u00f6m, M., Wu, X.: A completeness theory for polynomial (Turing) kernelization. Algorithmica 71(3), 702\u2013730 (2015)","journal-title":"Algorithmica"},{"key":"9_CR23","unstructured":"Jacob, H., Bellitto, T., Defrain, O., Pilipczuk, M.: Close relatives (of feedback vertex set), revisited. In: IPEC 2021, September 8\u201310, Lisbon, Portugal. LIPIcs, vol. 214, pp. 21:1\u201321:15. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik (2021)"},{"key":"9_CR24","doi-asserted-by":"publisher","first-page":"18","DOI":"10.1016\/j.jcss.2016.10.008","volume":"85","author":"BMP Jansen","year":"2017","unstructured":"Jansen, B.M.P.: Turing kernelization for finding long paths and cycles in restricted graph classes. J. Comput. Syst. Sci. 85, 18\u201337 (2017)","journal-title":"J. Comput. Syst. Sci."},{"key":"9_CR25","unstructured":"Jansen, B.M.P., Marx, D.: Characterizing the easy-to-find subgraphs from the viewpoint of polynomial-time algorithms, kernels, and Turing kernels. In: SODA 2015, San Diego, CA, USA, January 4\u20136, 2015. pp. 616\u2013629 (2015)"},{"issue":"10","key":"9_CR26","doi-asserted-by":"publisher","first-page":"3936","DOI":"10.1007\/s00453-019-00614-4","volume":"81","author":"BMP Jansen","year":"2019","unstructured":"Jansen, B.M.P., Pilipczuk, M., Wrochna, M.: Turing kernelization for finding long paths in graph classes excluding a topological minor. Algorithmica 81(10), 3936\u20133967 (2019)","journal-title":"Algorithmica"},{"key":"9_CR27","unstructured":"Kratsch, S., Nelles, F.: Efficient and adaptive parameterized algorithms on modular decompositions. In: ESA 2018, August 20\u201322, 2018, Helsinki, Finland. LIPIcs, vol. 112, pp. 55:1\u201355:15. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik (2018)"},{"key":"9_CR28","doi-asserted-by":"crossref","unstructured":"Lafond, M., Luo, W.: Preprocessing complexity for some graph problems parameterized by structural parameters. CoRR abs\/2306.12655 (2023)","DOI":"10.1016\/j.procs.2023.08.222"},{"key":"9_CR29","doi-asserted-by":"publisher","first-page":"87","DOI":"10.1016\/j.tcs.2021.12.017","volume":"905","author":"W Luo","year":"2022","unstructured":"Luo, W.: On some FPT problems without polynomial Turing compressions. Theor. Comput. Sci. 905, 87\u201398 (2022)","journal-title":"Theor. Comput. Sci."},{"key":"9_CR30","doi-asserted-by":"crossref","unstructured":"Luo, W.: Polynomial Turing compressions for some graph problems parameterized by modular-width. CoRR abs\/2201.04678 (2022)","DOI":"10.1007\/978-3-031-49190-0_9"},{"key":"9_CR31","unstructured":"Novick, M.B.: Fast parallel algorithms for the modular decomposition. Cornell University, Technical report (1989)"},{"issue":"5","key":"9_CR32","doi-asserted-by":"publisher","first-page":"883","DOI":"10.1007\/s11590-011-0311-5","volume":"6","author":"A Sch\u00e4fer","year":"2012","unstructured":"Sch\u00e4fer, A., Komusiewicz, C., Moser, H., Niedermeier, R.: Parameterized computational complexity of finding small-diameter subgraphs. Optim. Lett. 6(5), 883\u2013891 (2012)","journal-title":"Optim. Lett."},{"key":"9_CR33","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"634","DOI":"10.1007\/978-3-540-70575-8_52","volume-title":"Automata, Languages and Programming","author":"M Tedder","year":"2008","unstructured":"Tedder, M., Corneil, D., Habib, M., Paul, C.: Simpler linear-time modular decomposition via recursive factorizing permutations. In: Aceto, L., Damg\u00e5rd, I., Goldberg, L.A., Halld\u00f3rsson, M.M., Ing\u00f3lfsd\u00f3ttir, A., Walukiewicz, I. (eds.) ICALP 2008. LNCS, vol. 5125, pp. 634\u2013645. Springer, Heidelberg (2008). https:\/\/doi.org\/10.1007\/978-3-540-70575-8_52"},{"issue":"3","key":"9_CR34","doi-asserted-by":"publisher","first-page":"619","DOI":"10.1007\/s00453-015-0083-x","volume":"77","author":"S Thomass\u00e9","year":"2017","unstructured":"Thomass\u00e9, S., Trotignon, N., Vuskovic, K.: A polynomial Turing-kernel for weighted independent set in bull-free graphs. Algorithmica 77(3), 619\u2013641 (2017)","journal-title":"Algorithmica"},{"key":"9_CR35","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"504","DOI":"10.1007\/978-3-030-10801-4_39","volume-title":"SOFSEM 2019: Theory and Practice of Computer Science","author":"J Witteveen","year":"2019","unstructured":"Witteveen, J., Bottesch, R., Torenvliet, L.: A hierarchy of polynomial kernels. In: Catania, B., Kr\u00e1lovi\u010d, R., Nawrocki, J., Pighizzini, G. (eds.) SOFSEM 2019. LNCS, vol. 11376, pp. 504\u2013518. Springer, Cham (2019). https:\/\/doi.org\/10.1007\/978-3-030-10801-4_39"}],"container-title":["Lecture Notes in Computer Science","Computing and Combinatorics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-031-49190-0_9","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,12,27]],"date-time":"2023-12-27T17:36:00Z","timestamp":1703698560000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-031-49190-0_9"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,12,9]]},"ISBN":["9783031491894","9783031491900"],"references-count":35,"URL":"https:\/\/doi.org\/10.1007\/978-3-031-49190-0_9","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2023,12,9]]},"assertion":[{"value":"9 December 2023","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"COCOON","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"International Computing and Combinatorics Conference","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Hawaii, HI","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":"2023","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"15 December 2023","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"17 December 2023","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"29","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"cocoon2023","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"https:\/\/theory.utdallas.edu\/COCOON2023\/org.html","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Double-blind","order":1,"name":"type","label":"Type","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"Springer EquinOCS","order":2,"name":"conference_management_system","label":"Conference Management System","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"146","order":3,"name":"number_of_submissions_sent_for_review","label":"Number of Submissions Sent for Review","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"60","order":4,"name":"number_of_full_papers_accepted","label":"Number of Full Papers Accepted","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"0","order":5,"name":"number_of_short_papers_accepted","label":"Number of Short Papers Accepted","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"41% - The value is computed by the equation \"Number of Full Papers Accepted \/ Number of Submissions Sent for Review * 100\" and then rounded to a whole number.","order":6,"name":"acceptance_rate_of_full_papers","label":"Acceptance Rate of Full Papers","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"3","order":7,"name":"average_number_of_reviews_per_paper","label":"Average Number of Reviews per Paper","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"6","order":8,"name":"average_number_of_papers_per_reviewer","label":"Average Number of Papers per Reviewer","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"No","order":9,"name":"external_reviewers_involved","label":"External Reviewers Involved","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}}]}}