{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T14:39:11Z","timestamp":1787323151924,"version":"build-2736575974"},"reference-count":36,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"2","funder":[{"DOI":"10.13039\/501100001655","name":"Deutscher Akademischer Austauschdienst","doi-asserted-by":"publisher","id":[{"id":"10.13039\/501100001655","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100010661","name":"Horizon 2020 Framework Programme","doi-asserted-by":"publisher","award":["739574"],"award-info":[{"award-number":["739574"]}],"id":[{"id":"10.13039\/100010661","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100004329","name":"Javna Agencija za Raziskovalno Dejavnost RS","doi-asserted-by":"publisher","award":["BI-DE\/17-19-18"],"award-info":[{"award-number":["BI-DE\/17-19-18"]}],"id":[{"id":"10.13039\/501100004329","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100004329","name":"Javna Agencija za Raziskovalno Dejavnost RS","doi-asserted-by":"publisher","award":["BI-DE\/19-20-04"],"award-info":[{"award-number":["BI-DE\/19-20-04"]}],"id":[{"id":"10.13039\/501100004329","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100004329","name":"Javna Agencija za Raziskovalno Dejavnost RS","doi-asserted-by":"publisher","award":["P1-0285"],"award-info":[{"award-number":["P1-0285"]}],"id":[{"id":"10.13039\/501100004329","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100004329","name":"Javna Agencija za Raziskovalno Dejavnost RS","doi-asserted-by":"publisher","award":["N1-0102"],"award-info":[{"award-number":["N1-0102"]}],"id":[{"id":"10.13039\/501100004329","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100004329","name":"Javna Agencija za Raziskovalno Dejavnost RS","doi-asserted-by":"publisher","award":["J1-9110"],"award-info":[{"award-number":["J1-9110"]}],"id":[{"id":"10.13039\/501100004329","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Discrete Math."],"published-print":{"date-parts":[[2021,1]]},"abstract":"<jats:p>Graph searches and the corresponding search trees can exhibit important structural properties and are used in various graph algorithms. The problem of deciding whether a given spanning tree of a graph is a search tree of a particular search on this graph was introduced by Hagerup in 1985, where the author showed that this problem is efficiently solvable for depth first search (DFS) trees and breadth first search (BFS) trees. If one defines such a search tree in the same way as done for BFS, i.e., by connecting every vertex to its first neighbor, then we call this an ${\\cal F}$-tree. If, on the other hand, we connect it with its most recently visited neighbor (as in DFS) we call this an ${\\cal L}$-tree. In this paper, we consider related search paradigms. We prove that the search tree problem can be solved in polynomial time for ${\\cal L}$-trees of lexicographic depth first search, whereas the ${\\cal F}$-tree recognition problem is $\\mathcal{NP}$-complete for lexicographic breadth first search, lexicographic depth first search, maximum cardinality search, and maximal neighborhood search. Furthermore, we present polynomial results for both types of trees on chordal graphs.<\/jats:p>","DOI":"10.1137\/20m1313301","type":"journal-article","created":{"date-parts":[[2021,6,21]],"date-time":"2021-06-21T10:48:22Z","timestamp":1624272502000},"page":"1418-1446","source":"Crossref","is-referenced-by-count":6,"title":["The Recognition Problem of Graph Search Trees"],"prefix":"10.1137","volume":"35","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-8760-0169","authenticated-orcid":true,"given":"Jesse","family":"Beisegel","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Carolin","family":"Denkert","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Ekkehard","family":"K\u00f6hler","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-4960-8901","authenticated-orcid":true,"given":"Matja\u017e","family":"Krnc","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Nevena","family":"Piva\u010d","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Robert","family":"Scheffler","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Martin","family":"Strehler","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2021,6,21]]},"reference":[{"key":"atypb1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02122548"},{"key":"atypb2","first-page":"15","author":"Beisegel J.","year":"2018","journal-title":"Cham"},{"key":"atypb3","first-page":"10","volume":"21","author":"Beisegel J.","year":"2019","journal-title":"Discrete Math. Theor. Comput. Sci."},{"key":"atypb4","first-page":"99","author":"Beisegel J.","year":"2019","journal-title":"Ansterdam"},{"key":"atypb5","unstructured":"J. Beisegel, E. K\u00f6hler, R. Scheffler, and M. Strehler,\n                      Linear time LexDFS on chordal graphs\n                      , in 28th Annual European Symposium on Algorithms (ESA 2020), F. Grandoni, G. Herman, and P. Sanders, eds., LIPIcs Leibniz Int. Proc. Inform. 173, Dagstuhl, 2020, Schloss Dagstuhl-Leibniz-Zentrum f\u00fcr Informatik, pp. 13:1-13:13,https:\/\/doi.org\/10.4230\/LIPIcs.ESA.2020.13."},{"key":"atypb6","first-page":"57","volume":"16","author":"Charbit P.","year":"2014","journal-title":"Discrete Math. Theor. Comput. Sci."},{"key":"atypb7","doi-asserted-by":"publisher","DOI":"10.1137\/11083856X"},{"key":"atypb8","doi-asserted-by":"publisher","DOI":"10.1016\/j.dam.2009.10.001"},{"key":"atypb9","doi-asserted-by":"publisher","DOI":"10.1137\/050623498"},{"key":"atypb10","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539795282377"},{"key":"atypb11","doi-asserted-by":"publisher","DOI":"10.1137\/S0895480100373455"},{"key":"atypb12","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2012.09.018"},{"key":"atypb13","doi-asserted-by":"publisher","DOI":"10.1016\/j.dam.2015.07.016"},{"key":"atypb14","doi-asserted-by":"publisher","DOI":"10.1145\/321694.321699"},{"key":"atypb15","first-page":"46","author":"Even S.","year":"2012","journal-title":"New York"},{"key":"atypb16","unstructured":"M. R. Garey and D. S. Johnson,\n                      Computers and Intractability\n                      , 17th ed., W. H. Freeman, New York, 1995."},{"key":"atypb17","first-page":"98","author":"Golumbic M.","year":"2004","journal-title":"Amsterdam"},{"key":"atypb18","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(97)00241-7"},{"key":"atypb19","unstructured":"T. Hagerup,\n                      Biconnected Graph Assembly and Recognition of DFS Trees\n                      , Tech. Report A 85\/03, Universit\u00e4t des Saarlandes, 1985,https:\/\/doi.org\/10.22028\/D291-26437."},{"key":"atypb20","unstructured":"T. Hagerup and M. Nowak,\n                      Recognition of Spanning Trees Defined by Graph Searches\n                      , Tech. Report A 85\/08, Universit\u00e4t des Saarlandes, 1985."},{"key":"atypb21","doi-asserted-by":"publisher","DOI":"10.1145\/362248.362272"},{"key":"atypb22","doi-asserted-by":"publisher","DOI":"10.1145\/321850.321852"},{"key":"atypb23","first-page":"319","author":"K\u00f6hler E.","year":"2014","journal-title":"Cham"},{"key":"atypb24","first-page":"87","author":"Korach E.","year":"1989","journal-title":"Berlin"},{"key":"atypb25","doi-asserted-by":"publisher","DOI":"10.1016\/0012-365X(93)90375-4"},{"key":"atypb26","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(90)90155-Q"},{"key":"atypb27","doi-asserted-by":"publisher","DOI":"10.1109\/71.862207"},{"key":"atypb28","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(94)00126-X"},{"key":"atypb29","first-page":"499","author":"Prisner E.","year":"1997","journal-title":"Berlin"},{"key":"atypb30","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(85)90024-9"},{"key":"atypb31","doi-asserted-by":"publisher","DOI":"10.1137\/0205021"},{"key":"atypb32","doi-asserted-by":"publisher","DOI":"10.1016\/0166-218X(84)90008-8"},{"key":"atypb33","doi-asserted-by":"publisher","DOI":"10.1016\/0166-218X(93)E0161-Q"},{"key":"atypb34","doi-asserted-by":"publisher","DOI":"10.1137\/0201010"},{"key":"atypb35","doi-asserted-by":"publisher","DOI":"10.1007\/BF00268499"},{"key":"atypb36","doi-asserted-by":"publisher","DOI":"10.1137\/0213035"}],"container-title":["SIAM Journal on Discrete Mathematics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/20M1313301","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T13:44:59Z","timestamp":1787319899000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/20M1313301"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,1]]},"references-count":36,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2021,1]]}},"alternative-id":["10.1137\/20M1313301"],"URL":"https:\/\/doi.org\/10.1137\/20m1313301","relation":{},"ISSN":["0895-4801","1095-7146"],"issn-type":[{"value":"0895-4801","type":"print"},{"value":"1095-7146","type":"electronic"}],"subject":[],"published":{"date-parts":[[2021,1]]}}}