{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,2]],"date-time":"2026-01-02T00:45:12Z","timestamp":1767314712611,"version":"3.48.0"},"publisher-location":"Cham","reference-count":30,"publisher":"Springer Nature Switzerland","isbn-type":[{"value":"9783032118349","type":"print"},{"value":"9783032118356","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-3-032-11835-6_21","type":"book-chapter","created":{"date-parts":[[2026,1,2]],"date-time":"2026-01-02T00:41:42Z","timestamp":1767314502000},"page":"286-301","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["A Parameterized Complexity Analysis of\u00a0Bounded Height Depth-First Search Trees"],"prefix":"10.1007","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-4856-5863","authenticated-orcid":false,"given":"Lars","family":"Jaffke","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-9304-4536","authenticated-orcid":false,"given":"Paloma T.","family":"de Lima","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-8371-425X","authenticated-orcid":false,"given":"Wojciech","family":"Nadara","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-7900-3233","authenticated-orcid":false,"given":"Emmanuel","family":"Sam","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2026,1,2]]},"reference":[{"issue":"1","key":"21_CR1","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1006\/jagm.1993.1001","volume":"14","author":"HL Bodlaender","year":"1993","unstructured":"Bodlaender, H.L.: On linear time minor tests with depth-first search. J. Algorithms 14(1), 1\u201323 (1993)","journal-title":"J. Algorithms"},{"issue":"1","key":"21_CR2","doi-asserted-by":"publisher","first-page":"168","DOI":"10.1137\/S0895480195282550","volume":"11","author":"HL Bodlaender","year":"1998","unstructured":"Bodlaender, H.L., et al.: Rankings of graphs. SIAM J. Discret. Math. 11(1), 168\u2013181 (1998). https:\/\/doi.org\/10.1137\/S0895480195282550","journal-title":"SIAM J. Discret. Math."},{"issue":"2","key":"21_CR3","doi-asserted-by":"publisher","first-page":"238","DOI":"10.1006\/JAGM.1995.1009","volume":"18","author":"HL Bodlaender","year":"1995","unstructured":"Bodlaender, H.L., Gilbert, J.R., Hafsteinsson, H., Kloks, T.: Approximating treewidth, pathwidth, frontsize, and shortest elimination tree. J. Algorithms 18(2), 238\u2013255 (1995). https:\/\/doi.org\/10.1006\/JAGM.1995.1009","journal-title":"J. Algorithms"},{"issue":"4","key":"21_CR4","doi-asserted-by":"publisher","first-page":"696","DOI":"10.1137\/0116056","volume":"16","author":"G Chartrand","year":"1968","unstructured":"Chartrand, G., Kronk, H.V.: Randomly traceable graphs. SIAM J. Appl. Math. 16(4), 696\u2013700 (1968). https:\/\/doi.org\/10.1137\/0116056","journal-title":"SIAM J. Appl. Math."},{"key":"21_CR5","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":"21_CR6","doi-asserted-by":"publisher","unstructured":"Cygan, M., et al.: Parameterized Algorithms. Springer, Cham (2015). https:\/\/doi.org\/10.1007\/978-3-319-21275-3","DOI":"10.1007\/978-3-319-21275-3"},{"issue":"3","key":"21_CR7","doi-asserted-by":"publisher","first-page":"96","DOI":"10.1016\/j.ipl.2005.12.006","volume":"98","author":"D Dereniowski","year":"2006","unstructured":"Dereniowski, D., Nadolski, A.: Vertex rankings of chordal graphs and weighted trees. Inf. Process. Lett. 98(3), 96\u2013100 (2006). https:\/\/doi.org\/10.1016\/j.ipl.2005.12.006","journal-title":"Inf. Process. Lett."},{"key":"21_CR8","doi-asserted-by":"publisher","unstructured":"Downey, R.G., Fellows, M.R.: Fundamentals of Parameterized Complexity. Springer, Cham (2013). https:\/\/doi.org\/10.1007\/978-1-4471-5559-1","DOI":"10.1007\/978-1-4471-5559-1"},{"issue":"12","key":"21_CR9","doi-asserted-by":"publisher","first-page":"3597","DOI":"10.1007\/S00453-018-0408-7","volume":"80","author":"P Dvor\u00e1k","year":"2018","unstructured":"Dvor\u00e1k, P., Knop, D.: Parameterized complexity of length-bounded cuts and multicuts. Algorithmica 80(12), 3597\u20133617 (2018). https:\/\/doi.org\/10.1007\/S00453-018-0408-7","journal-title":"Algorithmica"},{"key":"21_CR10","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":"21_CR11","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":"21_CR12","doi-asserted-by":"publisher","first-page":"202","DOI":"10.1007\/S00453-014-9914-4","volume":"73","author":"FV Fomin","year":"2015","unstructured":"Fomin, F.V., Giannopoulou, A.C., Pilipczuk, M.: Computing tree-depth faster than $$2^n$$. Algorithmica 73(1), 202\u2013216 (2015). https:\/\/doi.org\/10.1007\/S00453-014-9914-4","journal-title":"Algorithmica"},{"key":"21_CR13","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, IJCAI 1985, vol. 2, pp. 1076\u20131078. Morgan Kaufmann Publishers Inc., San Francisco (1985)"},{"issue":"2","key":"21_CR14","doi-asserted-by":"publisher","first-page":"283","DOI":"10.1007\/S00224-017-9751-3","volume":"61","author":"M F\u00fcrer","year":"2017","unstructured":"F\u00fcrer, M., Yu, H.: Space saving by dynamic algebraization based on tree-depth. Theory Comput. Syst. 61(2), 283\u2013304 (2017). https:\/\/doi.org\/10.1007\/S00224-017-9751-3","journal-title":"Theory Comput. Syst."},{"key":"21_CR15","doi-asserted-by":"publisher","unstructured":"Ganian, R., Montecchiani, F., N\u00f6llenburg, M., Zehavi, M., Khazaliya, L.: New frontiers of parameterized complexity in graph drawing (Dagstuhl seminar 23162). Dagstuhl Rep. 13(4), 58\u201397 (2023). https:\/\/doi.org\/10.4230\/DagRep.13.4.58, https:\/\/drops.dagstuhl.de\/entities\/document\/10.4230\/DagRep.13.4.58","DOI":"10.4230\/DagRep.13.4.58"},{"key":"21_CR16","doi-asserted-by":"publisher","unstructured":"Hegerfeld, F., Kratsch, S.: Solving connectivity problems parameterized by treedepth in single-exponential time and polynomial space. In: Paul, C., Bl\u00e4ser, M. (eds.) Proceedings of the 37th International Symposium on Theoretical Aspects of Computer Science (STACS 2020). LIPIcs, vol.\u00a0154, pp. 29:1\u201329:16. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik (2020). https:\/\/doi.org\/10.4230\/LIPICS.STACS.2020.29","DOI":"10.4230\/LIPICS.STACS.2020.29"},{"key":"21_CR17","doi-asserted-by":"publisher","unstructured":"Jaffke, L., Lima, P.T., Nadara, W., Sam, E.: A parameterized complexity analysis of bounded height depth-first search trees. CoRR abs\/2502.16723 (2025). https:\/\/doi.org\/10.48550\/ARXIV.2502.16723","DOI":"10.48550\/ARXIV.2502.16723"},{"issue":"4","key":"21_CR18","doi-asserted-by":"publisher","first-page":"401","DOI":"10.7155\/JGAA.00601","volume":"26","author":"L Kellerhals","year":"2022","unstructured":"Kellerhals, L., Koana, T.: Parameterized complexity of geodetic set. J. Graph Algorithms Appl. 26(4), 401\u2013419 (2022). https:\/\/doi.org\/10.7155\/JGAA.00601","journal-title":"J. Graph Algorithms Appl."},{"key":"21_CR19","doi-asserted-by":"publisher","unstructured":"Kobayashi, Y., Tamaki, H.: Treedepth parameterized by vertex cover number. In: Guo, J., Hermelin, D. (eds.) Proceedings of the 11th International Symposium on Parameterized and Exact Computation (IPEC 2016). LIPIcs, vol.\u00a063, pp. 18:1\u201318:11. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik (2016). https:\/\/doi.org\/10.4230\/LIPICS.IPEC.2016.18","DOI":"10.4230\/LIPICS.IPEC.2016.18"},{"key":"21_CR20","doi-asserted-by":"publisher","unstructured":"Korhonen, T.: A single-exponential time 2-approximation algorithm for treewidth. In: Proceedings of the 62nd IEEE Annual Symposium on Foundations of Computer Science (FOCS 2021), pp. 184\u2013192. IEEE (2021). https:\/\/doi.org\/10.1109\/FOCS52979.2021.00026","DOI":"10.1109\/FOCS52979.2021.00026"},{"key":"21_CR21","doi-asserted-by":"publisher","unstructured":"Nadara, W., Pilipczuk, M., Smulewicz, M.: Computing treedepth in polynomial space and linear FPT time. In: Chechik, S., Navarro, G., Rotenberg, E., Herman, G. (eds.) Proceedings of the 30th Annual European Symposium on Algorithms (ESA 2022). LIPIcs, vol.\u00a0244, pp. 79:1\u201379:14. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik (2022). https:\/\/doi.org\/10.4230\/LIPICS.ESA.2022.79","DOI":"10.4230\/LIPICS.ESA.2022.79"},{"issue":"3","key":"21_CR22","doi-asserted-by":"publisher","first-page":"1566","DOI":"10.1137\/22M1518943","volume":"37","author":"J Nederlof","year":"2023","unstructured":"Nederlof, J., Pilipczuk, M., Swennenhuis, C.M.F., Wegrzycki, K.: Hamiltonian cycle parameterized by treedepth in single exponential time and polynomial space. SIAM J. Discret. Math. 37(3), 1566\u20131586 (2023). https:\/\/doi.org\/10.1137\/22M1518943","journal-title":"SIAM J. Discret. Math."},{"key":"21_CR23","doi-asserted-by":"publisher","unstructured":"Ne\u0161et\u0159il, J., Ossona de Mendez, P.: Bounded height trees and tree-depth. In: Ne\u0161et\u0159il, J., Ossona de Mendez, P. (eds.) Sparsity: Algorithms and Combinatorics, vol. 28, pp. 115\u2013144. Springer, Heidelberg (2012). https:\/\/doi.org\/10.1007\/978-3-642-27875-4_6","DOI":"10.1007\/978-3-642-27875-4_6"},{"key":"21_CR24","doi-asserted-by":"publisher","first-page":"111","DOI":"10.1016\/J.JCTB.2021.06.002","volume":"151","author":"M Pilipczuk","year":"2021","unstructured":"Pilipczuk, M., Siebertz, S.: Polynomial bounds for centered colorings on proper minor-closed graph classes. J. Comb. Theory B 151, 111\u2013147 (2021). https:\/\/doi.org\/10.1016\/J.JCTB.2021.06.002","journal-title":"J. Comb. Theory B"},{"key":"21_CR25","doi-asserted-by":"publisher","unstructured":"Pilipczuk, M., Wrochna, M.: On space efficiency of algorithms working on structural decompositions of graphs. ACM Trans. Comput. Theory 9(4), 18:1\u201318:36 (2018). https:\/\/doi.org\/10.1145\/3154856","DOI":"10.1145\/3154856"},{"key":"21_CR26","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"931","DOI":"10.1007\/978-3-662-43948-7_77","volume-title":"Automata, Languages, and Programming","author":"F Reidl","year":"2014","unstructured":"Reidl, F., Rossmanith, P., Villaamil, F.S., Sikdar, S.: A faster parameterized algorithm for treedepth. In: Esparza, J., Fraigniaud, P., Husfeldt, T., Koutsoupias, E. (eds.) ICALP 2014. LNCS, vol. 8572, pp. 931\u2013942. Springer, Heidelberg (2014). https:\/\/doi.org\/10.1007\/978-3-662-43948-7_77"},{"key":"21_CR27","doi-asserted-by":"publisher","unstructured":"Robertson, N., Seymour, P.D.: Graph minors. II. Algorithmic aspects of tree-width. J. Algorithms 7(3), 309\u2013322 (1986). https:\/\/doi.org\/10.1016\/0196-6774(86)90023-4, https:\/\/www.sciencedirect.com\/science\/article\/pii\/0196677486900234","DOI":"10.1016\/0196-6774(86)90023-4"},{"issue":"2","key":"21_CR28","doi-asserted-by":"publisher","first-page":"266","DOI":"10.1137\/0205021","volume":"5","author":"DJ Rose","year":"1976","unstructured":"Rose, D.J., Tarjan, R.E., Lueker, G.S.: Algorithmic aspects of vertex elimination on graphs. SIAM J. Comput. 5(2), 266\u2013283 (1976). https:\/\/doi.org\/10.1137\/0205021","journal-title":"SIAM J. Comput."},{"key":"21_CR29","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. In: Fernau, H., Jansen, K. (eds.) FCT 2023. LNCS, vol. 14292, pp. 392\u2013405. Springer, Cham (2023). https:\/\/doi.org\/10.1007\/978-3-031-43587-4_28","DOI":"10.1007\/978-3-031-43587-4_28"},{"key":"21_CR30","doi-asserted-by":"publisher","unstructured":"Sam, E., Fellows, M.R., Rosamond, F.A., 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.) CIAC 2023. LNCS, vol. 13898, pp. 353\u2013367. Springer, Cham (2023). https:\/\/doi.org\/10.1007\/978-3-031-30448-4_25","DOI":"10.1007\/978-3-031-30448-4_25"}],"container-title":["Lecture Notes in Computer Science","Graph-Theoretic Concepts in Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-032-11835-6_21","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,1,2]],"date-time":"2026-01-02T00:41:44Z","timestamp":1767314504000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-032-11835-6_21"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2026]]},"ISBN":["9783032118349","9783032118356"],"references-count":30,"URL":"https:\/\/doi.org\/10.1007\/978-3-032-11835-6_21","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":"2 January 2026","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"The authors have no competing interests.","order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Disclosure of Interests"}},{"value":"WG","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"International Workshop on Graph-Theoretic Concepts in Computer Science","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Otzenhausen","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":"2025","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"11 June 2025","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"13 June 2025","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"51","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"wg2025","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"https:\/\/algo.uni-trier.de\/wg2025\/","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}}]}}