{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,2]],"date-time":"2026-01-02T07:27:28Z","timestamp":1767338848887,"version":"3.40.3"},"publisher-location":"Cham","reference-count":30,"publisher":"Springer Nature Switzerland","isbn-type":[{"type":"print","value":"9783031435867"},{"type":"electronic","value":"9783031435874"}],"license":[{"start":{"date-parts":[[2023,1,1]],"date-time":"2023-01-01T00:00:00Z","timestamp":1672531200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2023,1,1]],"date-time":"2023-01-01T00:00:00Z","timestamp":1672531200000},"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":[[2023]]},"DOI":"10.1007\/978-3-031-43587-4_28","type":"book-chapter","created":{"date-parts":[[2023,9,21]],"date-time":"2023-09-21T01:02:10Z","timestamp":1695258130000},"page":"392-405","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":2,"title":["Kernelization for\u00a0Finding Lineal Topologies (Depth-First Spanning Trees) with\u00a0Many or\u00a0Few Leaves"],"prefix":"10.1007","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-7756-0901","authenticated-orcid":false,"given":"Emmanuel","family":"Sam","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-6270-3663","authenticated-orcid":false,"given":"Benjamin","family":"Bergougnoux","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-2619-2990","authenticated-orcid":false,"given":"Petr A.","family":"Golovach","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-9489-1657","authenticated-orcid":false,"given":"Nello","family":"Blaser","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2023,9,21]]},"reference":[{"issue":"3","key":"28_CR1","doi-asserted-by":"publisher","first-page":"167","DOI":"10.1016\/S0925-7721(01)00006-2","volume":"18","author":"T Biedl","year":"2001","unstructured":"Biedl, T.: The DFS-heuristic for orthogonal graph drawing. Comput. Geom. 18(3), 167\u2013188 (2001). https:\/\/doi.org\/10.1016\/S0925-7721(01)00006-2","journal-title":"Comput. Geom."},{"key":"28_CR2","doi-asserted-by":"publisher","first-page":"531","DOI":"10.1007\/978-3-540-78773-0_46","volume-title":"LATIN 2008: Theoretical Informatics","author":"P Bonsma","year":"2008","unstructured":"Bonsma, P., Zickfeld, F.: Spanning trees with many leaves in graphs without diamonds and blossoms. In: Laber, E.S., Bornstein, C., Nogueira, L.T., Faria, L. (eds.) LATIN 2008: Theoretical Informatics, pp. 531\u2013543. Springer, Berlin, Heidelberg (2008). https:\/\/doi.org\/10.1007\/978-3-540-78773-0_46"},{"key":"28_CR3","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"259","DOI":"10.1007\/978-3-540-45138-9_20","volume-title":"Mathematical Foundations of Computer Science 2003","author":"PS Bonsma","year":"2003","unstructured":"Bonsma, P.S., Brueggemann, T., Woeginger, G.J.: A faster FPT algorithm for finding spanning trees with many leaves. In: Rovan, B., Vojt\u00e1\u0161, P. (eds.) MFCS 2003. LNCS, vol. 2747, pp. 259\u2013268. Springer, Heidelberg (2003). https:\/\/doi.org\/10.1007\/978-3-540-45138-9_20"},{"issue":"1","key":"28_CR4","doi-asserted-by":"publisher","first-page":"219","DOI":"10.1016\/S0012-365X(96)00306-8","volume":"170","author":"T B\u00f6hme","year":"1997","unstructured":"B\u00f6hme, T., Broersma, H., G\u00f6bel, F., Kostochka, A., Stiebitz, M.: Spanning trees with pairwise nonadjacent endvertices. Discrete Math. 170(1), 219\u2013222 (1997). https:\/\/doi.org\/10.1016\/S0012-365X(96)00306-8","journal-title":"Discrete Math."},{"key":"28_CR5","doi-asserted-by":"publisher","unstructured":"Casel, K., et al.: Complexity of independency and Cliquy trees. Discrete Appl. Math. 272, 2\u201315 (2020). https:\/\/doi.org\/10.1016\/j.dam.2018.08.011, 15th Cologne-Twente Workshop on Graphs and Combinatorial Optimization (CTW 2017)","DOI":"10.1016\/j.dam.2018.08.011"},{"key":"28_CR6","unstructured":"Cormen, T.H., Leiserson, C.E., Rivest, R.L., Stein, C.: Introduction to Algorithms, Third Edition. The MIT Press, 3rd edn. (2009)"},{"key":"28_CR7","doi-asserted-by":"publisher","unstructured":"Courcelle, B.: The monadic second-order logic of graphs. i. recognizable sets of finite graphs. Inf. Comput. 85(1), 12\u201375 (1990). https:\/\/doi.org\/10.1016\/0890-5401(90)90043-H","DOI":"10.1016\/0890-5401(90)90043-H"},{"key":"28_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, 1st edn. Springer Publishing Company, Incorporated (2015). https:\/\/doi.org\/10.1007\/978-3-319-21275-3","edition":"1"},{"key":"28_CR9","doi-asserted-by":"publisher","first-page":"169","DOI":"10.1016\/j.endm.2008.06.035","volume":"31","author":"H De Fraysseix","year":"2008","unstructured":"De Fraysseix, H.: Tr\u00e9maux trees and planarity. Electron. Notes Discrete Math. 31, 169\u2013180 (2008)","journal-title":"Electron. Notes Discrete Math."},{"key":"28_CR10","doi-asserted-by":"publisher","unstructured":"de Fraysseix, H., Ossona de Mendez, P.: Tr\u00e9maux trees and planarity. Eur. J. Comb. 33(3), 279\u2013293 (2012). https:\/\/doi.org\/10.1016\/j.ejc.2011.09.012, topological and Geometric Graph Theory","DOI":"10.1016\/j.ejc.2011.09.012"},{"key":"28_CR11","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-53622-3","volume-title":"Graph Theory","author":"R Diestel","year":"2017","unstructured":"Diestel, R.: Graph Theory, 5th edn. Springer Publishing Company, Incorporated (2017). https:\/\/doi.org\/10.1007\/978-3-662-53622-3","edition":"5"},{"key":"28_CR12","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. Springer Publishing Company, Incorporated (2013). https:\/\/doi.org\/10.1007\/978-1-4471-5559-1"},{"key":"28_CR13","unstructured":"Estivill-Castro, V., Fellows, M.R., Langston, M.A., Rosamond, F.A.: FPT is p-time extremal structure I. In: Broersma, H., Johnson, M., Szeider, S. (eds.) Algorithms and Complexity in Durham 2005 - Proceedings of the First ACiD Workshop, 8\u201310 July 2005, Durham, UK. Texts in Algorithmics, vol. 4, pp. 1\u201341. King\u2019s College, London (2005)"},{"issue":"1\u20134","key":"28_CR14","doi-asserted-by":"publisher","first-page":"549","DOI":"10.1007\/BF01762131","volume":"3","author":"MR Fellows","year":"1988","unstructured":"Fellows, M.R., Friesen, D.K., Langston, M.A.: On finding optimal and near-optimal lineal spanning trees. Algorithmica 3(1\u20134), 549\u2013560 (1988)","journal-title":"Algorithmica"},{"issue":"1","key":"28_CR15","doi-asserted-by":"publisher","first-page":"117","DOI":"10.1137\/0405010","volume":"5","author":"MR Fellows","year":"1992","unstructured":"Fellows, M.R., Langston, M.A.: On well-partial-order theory and its application to combinatorial problems of VLSI design. SIAM J. Discrete Math. 5(1), 117\u2013126 (1992)","journal-title":"SIAM J. Discrete Math."},{"key":"28_CR16","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"275","DOI":"10.1007\/978-3-642-10631-6_29","volume-title":"Algorithms and Computation","author":"FV Fomin","year":"2009","unstructured":"Fomin, F.V., Gaspers, S., Saurabh, S., Thomass\u00e9, S.: A linear vertex kernel for Maximum Internal Spanning Tree. In: Dong, Y., Du, D.-Z., Ibarra, O. (eds.) ISAAC 2009. LNCS, vol. 5878, pp. 275\u2013282. Springer, Heidelberg (2009). https:\/\/doi.org\/10.1007\/978-3-642-10631-6_29"},{"key":"28_CR17","unstructured":"Freuder, E.C., Quinn, M.J.: Taking advantage of stable sets of variables in constraint satisfaction problems. In: Proceedings of the 9th International Joint Conference on Artificial Intelligence - Vol. 2. pp. 1076\u20131078. IJCAI\u201985, Morgan Kaufmann Publishers Inc., San Francisco, CA, USA (1985)"},{"key":"28_CR18","unstructured":"Garey, M.R., Johnson, D.S.: Computers and Intractability; A Guide to the Theory of NP-Completeness. W. H. Freeman & Co., USA (1990)"},{"issue":"6","key":"28_CR19","doi-asserted-by":"publisher","first-page":"372","DOI":"10.1145\/362248.362272","volume":"16","author":"J Hopcroft","year":"1973","unstructured":"Hopcroft, J., Tarjan, R.: Algorithm 447: efficient algorithms for graph manipulation. Commun. ACM 16(6), 372\u2013378 (1973)","journal-title":"Commun. ACM"},{"issue":"4","key":"28_CR20","doi-asserted-by":"publisher","first-page":"549","DOI":"10.1145\/321850.321852","volume":"21","author":"J Hopcroft","year":"1974","unstructured":"Hopcroft, J., Tarjan, R.: Efficient planarity testing. J. ACM (JACM) 21(4), 549\u2013568 (1974)","journal-title":"J. ACM (JACM)"},{"issue":"4","key":"28_CR21","doi-asserted-by":"publisher","first-page":"225","DOI":"10.1137\/0202019","volume":"2","author":"JE Hopcroft","year":"1973","unstructured":"Hopcroft, J.E., Karp, R.M.: An n$${}^{\\text{5\/2 }}$$ algorithm for maximum matchings in bipartite graphs. SIAM J. Comput. 2(4), 225\u2013231 (1973). https:\/\/doi.org\/10.1137\/0202019","journal-title":"SIAM J. Comput."},{"key":"28_CR22","doi-asserted-by":"publisher","first-page":"187","DOI":"10.1016\/j.ic.2016.11.003","volume":"252","author":"W Li","year":"2017","unstructured":"Li, W., Cao, Y., Chen, J., Wang, J.: Deeper local search for parameterized and approximation algorithms for maximum internal spanning tree. Inf. Comput. 252, 187\u2013200 (2017)","journal-title":"Inf. Comput."},{"key":"28_CR23","unstructured":"Lu, H.I., Ravi, R.: The power of local optimization: approximation algorithms for maximum-leaf spanning tree. In: Proceedings, Thirtieth Annual Allerton Conference on Communication, Control and Computing, pp. 533\u2013542 (1996)"},{"key":"28_CR24","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"240","DOI":"10.1007\/3-540-44450-5_19","volume-title":"FST TCS 2000: Foundations of Software Technology and Theoretical Computer Science","author":"RF Michael","year":"2000","unstructured":"Michael, R.F., McCartin, C., Frances, A.R., Stege, U.: Coordinatized kernels and catalytic reductions: an improved FPT algorithm for max leaf spanning tree and other problems. In: Kapoor, S., Prasad, S. (eds.) FSTTCS 2000. LNCS, vol. 1974, pp. 240\u2013251. Springer, Heidelberg (2000). https:\/\/doi.org\/10.1007\/3-540-44450-5_19"},{"key":"28_CR25","series-title":"Algorithms and Combinatorics","doi-asserted-by":"publisher","first-page":"115","DOI":"10.1007\/978-3-642-27875-4_6","volume-title":"Sparsity","author":"J Ne\u0161et\u0159il","year":"2012","unstructured":"Ne\u0161et\u0159il, J., de Mendez, P.O.: Bounded height trees and tree-depth. In: Sparsity. AC, vol. 28, pp. 115\u2013144. Springer, Heidelberg (2012). https:\/\/doi.org\/10.1007\/978-3-642-27875-4_6"},{"key":"28_CR26","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"474","DOI":"10.1007\/978-3-540-45078-8_41","volume-title":"Algorithms and Data Structures","author":"E Prieto","year":"2003","unstructured":"Prieto, E., Sloper, C.: Either\/Or: using Vertex Cover structure in designing FPT-algorithms \u2014 the case of k-Internal Spanning Tree. In: Dehne, F., Sack, J.-R., Smid, M. (eds.) WADS 2003. LNCS, vol. 2748, pp. 474\u2013483. Springer, Heidelberg (2003). https:\/\/doi.org\/10.1007\/978-3-540-45078-8_41"},{"issue":"2","key":"28_CR27","doi-asserted-by":"publisher","first-page":"93","DOI":"10.1016\/j.ipl.2004.12.016","volume":"94","author":"MS Rahman","year":"2005","unstructured":"Rahman, M.S., Kaykobad, M.: Complexities of some interesting problems on spanning trees. Inf. Process. Lett. 94(2), 93\u201397 (2005). https:\/\/doi.org\/10.1016\/j.ipl.2004.12.016","journal-title":"Inf. Process. Lett."},{"key":"28_CR28","doi-asserted-by":"publisher","unstructured":"Sam, E., Bergougnoux, B., Golovach, P.A., Blaser, N.: Kernelization for finding lineal topologies (depth-first spanning trees) with many or few leaves (2023). https:\/\/doi.org\/10.48550\/arXiv.2307.00362","DOI":"10.48550\/arXiv.2307.00362"},{"key":"28_CR29","doi-asserted-by":"publisher","first-page":"353","DOI":"10.1007\/978-3-031-30448-4_25","volume-title":"Algorithms and Complexity","author":"E Sam","year":"2023","unstructured":"Sam, E., Fellows, M., Rosamond, F., Golovach, P.A.: On the parameterized complexity of the structure of lineal topologies (depth-first spanning trees) of finite graphs: The number of leaves. In: Mavronicolas, M. (ed.) Algorithms and Complexity, pp. 353\u2013367. Springer International Publishing, Cham (2023). https:\/\/doi.org\/10.1007\/978-3-031-30448-4_25"},{"key":"28_CR30","doi-asserted-by":"publisher","unstructured":"Tarjan, R.: Depth-first search and linear graph algorithms. In: 12th Annual Symposium on Switching and Automata Theory (swat 1971), pp. 114\u2013121 (1971). https:\/\/doi.org\/10.1109\/SWAT.1971.10","DOI":"10.1109\/SWAT.1971.10"}],"container-title":["Lecture Notes in Computer Science","Fundamentals of Computation Theory"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-031-43587-4_28","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,11,13]],"date-time":"2023-11-13T21:37:34Z","timestamp":1699911454000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-031-43587-4_28"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023]]},"ISBN":["9783031435867","9783031435874"],"references-count":30,"URL":"https:\/\/doi.org\/10.1007\/978-3-031-43587-4_28","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2023]]},"assertion":[{"value":"21 September 2023","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"FCT","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"International Symposium on Fundamentals of Computation Theory","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Trier","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Germany","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":"18 September 2023","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"21 September 2023","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"24","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"fct2023","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"https:\/\/www.uni-trier.de\/index.php?id=71937&L=2","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Single-blind","order":1,"name":"type","label":"Type","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"EquinOCS","order":2,"name":"conference_management_system","label":"Conference Management System","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"69","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":"30","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":"43% - 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":"3","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":"Yes","order":9,"name":"external_reviewers_involved","label":"External Reviewers Involved","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}}]}}