{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,2]],"date-time":"2026-01-02T07:27:50Z","timestamp":1767338870494,"version":"3.40.3"},"publisher-location":"Cham","reference-count":29,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783031304477"},{"type":"electronic","value":"9783031304484"}],"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-30448-4_25","type":"book-chapter","created":{"date-parts":[[2023,4,24]],"date-time":"2023-04-24T20:29:36Z","timestamp":1682368176000},"page":"353-367","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":2,"title":["On the\u00a0Parameterized Complexity of\u00a0the\u00a0Structure of\u00a0Lineal Topologies (Depth-First Spanning Trees) of\u00a0Finite Graphs: The Number of\u00a0Leaves"],"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-6148-9212","authenticated-orcid":false,"given":"Michael","family":"Fellows","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-5097-9929","authenticated-orcid":false,"given":"Frances","family":"Rosamond","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"}]}],"member":"297","published-online":{"date-parts":[[2023,4,25]]},"reference":[{"issue":"1","key":"25_CR1","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1006\/jagm.1993.1001","volume":"14","author":"H Bodlaender","year":"1993","unstructured":"Bodlaender, H.: On linear time minor tests with depth-first search. J. Algorithms 14(1), 1\u201323 (1993)","journal-title":"J. Algorithms"},{"key":"25_CR2","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":"3","key":"25_CR3","doi-asserted-by":"publisher","first-page":"223","DOI":"10.1002\/jgt.3190060302","volume":"6","author":"PZ Chinn","year":"1982","unstructured":"Chinn, P.Z., Chv\u00e1talov\u00e1, J., Dewdney, A.K., Gibbs, N.E.: The bandwidth problem for graphs and matrices-a survey. J. Graph Theory 6(3), 223\u2013254 (1982)","journal-title":"J. Graph Theory"},{"issue":"1","key":"25_CR4","doi-asserted-by":"publisher","first-page":"12","DOI":"10.1016\/0890-5401(90)90043-H","volume":"85","author":"B Courcelle","year":"1990","unstructured":"Courcelle, B.: The monadic second-order logic of graphs. I. Recognizable sets of finite graphs. Inf. Comput. 85(1), 12\u201375 (1990)","journal-title":"Inf. Comput."},{"issue":"2","key":"25_CR5","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). https:\/\/doi.org\/10.1007\/s002249910009","journal-title":"Theory Comput. Syst."},{"key":"25_CR6","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511977619","volume-title":"Graph Structure and Monadic Second-Order Logic: A Language-Theoretic Approach","author":"PB Courcelle","year":"2012","unstructured":"Courcelle, P.B., Engelfriet, D.J.: Graph Structure and Monadic Second-Order Logic: A Language-Theoretic Approach, 1st edn. Cambridge University Press, Cambridge (2012)","edition":"1"},{"key":"25_CR7","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, Cham (2015). https:\/\/doi.org\/10.1007\/978-3-319-21275-3","edition":"1"},{"key":"25_CR8","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."},{"issue":"05","key":"25_CR9","doi-asserted-by":"publisher","first-page":"1017","DOI":"10.1142\/S0129054106004248","volume":"17","author":"H De Fraysseix","year":"2006","unstructured":"De Fraysseix, H., De Mendez, P.O., Rosenstiehl, P.: Tr\u00e9maux trees and planarity. Int. J. Found. Comput. Sci. 17(05), 1017\u20131029 (2006)","journal-title":"Int. J. Found. Comput. Sci."},{"key":"25_CR10","doi-asserted-by":"crossref","unstructured":"de Fraysseix, H., de Mendez, P.O.: Tr\u00e9maux trees and planarity. Eur. J. Comb. 33(3), 279\u2013293 (2012). Topological and Geometric Graph Theory","DOI":"10.1016\/j.ejc.2011.09.012"},{"key":"25_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, Heidelberg (2017). https:\/\/doi.org\/10.1007\/978-3-662-53622-3","edition":"5"},{"issue":"1","key":"25_CR12","doi-asserted-by":"publisher","first-page":"16","DOI":"10.1112\/S0024610700001708","volume":"63","author":"R Diestel","year":"2001","unstructured":"Diestel, R., Leader, I.: Normal spanning trees, Aronszajn trees and excluded minors. J. Lond. Math. Soc. 63(1), 16\u201332 (2001)","journal-title":"J. Lond. Math. Soc."},{"issue":"4","key":"25_CR13","doi-asserted-by":"publisher","first-page":"873","DOI":"10.1137\/S0097539792228228","volume":"24","author":"RG Downey","year":"1995","unstructured":"Downey, R.G., Fellows, M.R.: Fixed-parameter tractability and completeness I: basic results. SIAM J. Comput. 24(4), 873\u2013921 (1995)","journal-title":"SIAM J. Comput."},{"key":"25_CR14","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, London (2013). https:\/\/doi.org\/10.1007\/978-1-4471-5559-1"},{"issue":"4","key":"25_CR15","doi-asserted-by":"publisher","first-page":"507","DOI":"10.1137\/0204043","volume":"4","author":"S Even","year":"1975","unstructured":"Even, S., Tarjan, R.E.: Network flow and testing graph connectivity. SIAM J. Comput. 4(4), 507\u2013518 (1975)","journal-title":"SIAM J. Comput."},{"key":"25_CR16","doi-asserted-by":"publisher","unstructured":"Fellows, M.R., Langston, M.A.: On search decision and the efficiency of polynomial-time algorithms. In: Proceedings of the Twenty-First Annual ACM Symposium on Theory of Computing, STOC 1989, pp. 501\u2013512. Association for Computing Machinery, New York (1989). https:\/\/doi.org\/10.1145\/73007.73055","DOI":"10.1145\/73007.73055"},{"issue":"1\u20134","key":"25_CR17","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). https:\/\/doi.org\/10.1007\/BF01762131","journal-title":"Algorithmica"},{"key":"25_CR18","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"7","DOI":"10.1007\/978-3-030-42071-0_2","volume-title":"Treewidth, Kernels, and Algorithms","author":"MR Fellows","year":"2020","unstructured":"Fellows, M.R., Rosamond, F.A.: Collaborating with Hans: some remaining wonderments. In: Fomin, F.V., Kratsch, S., van Leeuwen, E.J. (eds.) Treewidth, Kernels, and Algorithms. LNCS, vol. 12160, pp. 7\u201317. Springer, Cham (2020). https:\/\/doi.org\/10.1007\/978-3-030-42071-0_2"},{"issue":"2","key":"25_CR19","doi-asserted-by":"publisher","first-page":"127","DOI":"10.1007\/BF02579375","volume":"5","author":"H de Fraysseix","year":"1985","unstructured":"de Fraysseix, H., Rosenstiehl, P.: A characterization of planar graphs by Tr\u00e9maux orders. Combinatorica 5(2), 127\u2013135 (1985). https:\/\/doi.org\/10.1007\/BF02579375","journal-title":"Combinatorica"},{"issue":"3","key":"25_CR20","doi-asserted-by":"publisher","first-page":"312","DOI":"10.1137\/0604033","volume":"4","author":"MR Garey","year":"1983","unstructured":"Garey, M.R., Johnson, D.S.: Crossing number is NP-complete. SIAM J. Algebraic Discrete Methods 4(3), 312\u2013316 (1983). https:\/\/doi.org\/10.1137\/0604033","journal-title":"SIAM J. Algebraic Discrete Methods"},{"issue":"6","key":"25_CR21","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":"25_CR22","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":"25_CR23","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^{5\/2}$$ algorithm for maximum matchings in bipartite graphs. SIAM J. Comput. 2(4), 225\u2013231 (1973)","journal-title":"SIAM J. Comput."},{"key":"25_CR24","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-07003-1","volume-title":"Elements of Finite Model Theory","author":"L Libkin","year":"2004","unstructured":"Libkin, L.: Elements of Finite Model Theory. Springer, Heidelberg (2004). https:\/\/doi.org\/10.1007\/978-3-662-07003-1"},{"key":"25_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: Ne\u0161et\u0159il, J., de Mendez, P.O. (eds.) Sparsity. AC, vol. 28, pp. 115\u2013144. Springer, Heidelberg (2012). https:\/\/doi.org\/10.1007\/978-3-642-27875-4_6"},{"key":"25_CR26","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/s00373-010-0973-2","volume":"27","author":"K Ozeki","year":"2011","unstructured":"Ozeki, K., Yamashita, T.: Spanning trees: a survey. Graphs Comb. 27, 1\u201326 (2011). https:\/\/doi.org\/10.1007\/s00373-010-0973-2","journal-title":"Graphs Comb."},{"key":"25_CR27","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\u2014the 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"},{"key":"25_CR28","doi-asserted-by":"publisher","first-page":"1211","DOI":"10.1007\/978-1-4939-2864-4_228","volume-title":"Encyclopedia of Algorithms","author":"F Rosamond","year":"2016","unstructured":"Rosamond, F.: Max leaf spanning tree. In: Kao, M.Y. (ed.) Encyclopedia of Algorithms, pp. 1211\u20131215. Springer, New York (2016). https:\/\/doi.org\/10.1007\/978-1-4939-2864-4_228"},{"key":"25_CR29","unstructured":"Williamson, S.: Combinatorics for Computer Science. Dover Books on Mathematics. Dover Publications (2002). https:\/\/books.google.no\/books?id=YMIoy5JwdHMC"}],"container-title":["Lecture Notes in Computer Science","Algorithms and Complexity"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-031-30448-4_25","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,5,15]],"date-time":"2023-05-15T23:04:35Z","timestamp":1684191875000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-031-30448-4_25"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023]]},"ISBN":["9783031304477","9783031304484"],"references-count":29,"URL":"https:\/\/doi.org\/10.1007\/978-3-031-30448-4_25","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":"25 April 2023","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"CIAC","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"International Conference on Algorithms and Complexity","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Larnaca","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Cyprus","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":"13 June 2023","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"16 June 2023","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"13","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"ciac2023","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Open","order":1,"name":"type","label":"Type","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"Easy Chair","order":2,"name":"conference_management_system","label":"Conference Management System","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"49","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":"25","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":"51% - 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":"Yes","order":9,"name":"external_reviewers_involved","label":"External Reviewers Involved","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"3 invited papers","order":10,"name":"additional_info_on_review_process","label":"Additional Info on Review Process","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}}]}}