{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,7]],"date-time":"2026-06-07T08:52:22Z","timestamp":1780822342514,"version":"3.54.1"},"publisher-location":"Berlin, Heidelberg","reference-count":17,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783540507284","type":"print"},{"value":"9783540460763","type":"electronic"}],"license":[{"start":{"date-parts":[[1989,1,1]],"date-time":"1989-01-01T00:00:00Z","timestamp":599616000000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1989]]},"DOI":"10.1007\/3-540-50728-0_37","type":"book-chapter","created":{"date-parts":[[2012,2,25]],"date-time":"2012-02-25T20:33:21Z","timestamp":1330202001000},"page":"87-106","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":8,"title":["DFS tree construction: Algorithms and characterizations"],"prefix":"10.1007","author":[{"given":"Ephraim","family":"Korach","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Zvi","family":"Ostfeld","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2005,5,31]]},"reference":[{"key":"6_CR1","doi-asserted-by":"crossref","unstructured":"A. Aggarwal and R.J. Anderson, A random NC algorithm for depth-first search, In Proc. of the 19th ACM Symposium on Theory of Computation, 325\u2013334, (1987). To appear in Combinatorica.","DOI":"10.1145\/28395.28430"},{"issue":"3","key":"6_CR2","doi-asserted-by":"crossref","first-page":"147","DOI":"10.1016\/0020-0190(85)90083-3","volume":"20","author":"B. Awerbuch","year":"1985","unstructured":"B. Awerbuch, A new distributed depth-first-search algorithm, Information Processing Letters, 20 (3), 147\u2013150, (1985).","journal-title":"Information Processing Letters"},{"key":"6_CR3","volume-title":"Graph Theory 1736\u20131936","author":"N.L. Biggs","year":"1977","unstructured":"N.L. Biggs, E.K. Lyod and R.J. Wilson, Graph Theory 1736\u20131936, Clarendon Press, Oxford, (1977)."},{"key":"6_CR4","volume-title":"Graph Algorithms","author":"S. Even","year":"1979","unstructured":"S. Even, Graph Algorithms, Computer Science Press, Potomac, MD, (1979)."},{"key":"6_CR5","unstructured":"T. Hagerup and M. Nowak, Recognition of Spanning Trees Defined by Graph Searches, Technical Report A 85\/08, Universit\u00e4t des Saarlandes, Saarbr\u00fccken, West Germany, June 1985."},{"key":"6_CR6","doi-asserted-by":"crossref","unstructured":"J.E. Hopcroft and R.E. Tarjan, Dividing a graph into triconnected components, SIAM Journal on Computing, 2(3), (1973).","DOI":"10.1137\/0202012"},{"issue":"6","key":"6_CR7","doi-asserted-by":"crossref","first-page":"372","DOI":"10.1145\/362248.362272","volume":"16","author":"J.E. Hopcroft","year":"1973","unstructured":"J.E. Hopcroft and R.E. Tarjan, Efficient algorithms for graph manipulation, Comm. ACM, 16(6), 372\u2013378, (1973).","journal-title":"Comm. ACM"},{"key":"6_CR8","doi-asserted-by":"crossref","first-page":"549","DOI":"10.1145\/321850.321852","volume":"21","author":"J.E. Hopcroft","year":"1974","unstructured":"J.E. Hopcroft and R.E. Tarjan, Efficient planarity testing, J. ACM, 21, 549\u2013568, (1974).","journal-title":"J. ACM"},{"key":"6_CR9","unstructured":"E. Korach and Z. Ostfeld, On the Possibilities of DFS Tree Constructions: Sequential and Parallel Algorithms, Technical Report no. 508, CS Dept. Technion, May 1988."},{"key":"6_CR10","doi-asserted-by":"crossref","first-page":"103","DOI":"10.1016\/0020-0190(87)90228-6","volume":"25","author":"K.B. Lakshmanan","year":"1987","unstructured":"K.B. Lakshmanan, N. Meenakshi and K. Thulasiraman, A time-optimal message-efficient distributed algorithm for Depth-first-Search, Information Processing Letters, 25, 103\u2013109, (1987).","journal-title":"Information Processing Letters"},{"key":"6_CR11","doi-asserted-by":"crossref","first-page":"507","DOI":"10.1002\/net.3230140403","volume":"14","author":"A. LaPaugh","year":"1984","unstructured":"A. LaPaugh and C.H. Papadimitriou, The even-path problem for graphs and digraphs, Networks, 14, 507\u2013513, (1984).","journal-title":"Networks"},{"key":"6_CR12","doi-asserted-by":"crossref","first-page":"229","DOI":"10.1016\/0020-0190(85)90024-9","volume":"20","author":"J.H. Reif","year":"1985","unstructured":"J.H. Reif, Depth-first search is inherently sequential, Information Processing Letters, 20, 229\u2013234, (1985).","journal-title":"Information Processing Letters"},{"issue":"12","key":"6_CR13","doi-asserted-by":"crossref","first-page":"1029","DOI":"10.1109\/TCS.1984.1085460","volume":"31","author":"M.M. Syslo","year":"1984","unstructured":"M.M. Syslo, Series-parallel graphs and depth-first search trees, IEEE Transactions on Circuits and Systems, 31(12), 1029\u20131033, (1984).","journal-title":"IEEE Transactions on Circuits and Systems"},{"issue":"4","key":"6_CR14","doi-asserted-by":"crossref","first-page":"862","DOI":"10.1137\/0214061","volume":"14","author":"R.E. Tarjan","year":"1985","unstructured":"R.E. Tarjan and U. Vishkin, An efficient parallel biconnectivity algorithm, SIAM Journal on Computing, 14(4), 862\u2013874, (1985).","journal-title":"SIAM Journal on Computing"},{"key":"6_CR15","doi-asserted-by":"crossref","first-page":"146","DOI":"10.1137\/0201010","volume":"1","author":"R.E. Tarjan","year":"1972","unstructured":"R.E. Tarjan, Depth-first search and linear graph algorithms, SIAM Journal on Computing, 1, 146\u2013160, (1972).","journal-title":"SIAM Journal on Computing"},{"key":"6_CR16","doi-asserted-by":"crossref","first-page":"105","DOI":"10.1016\/0196-6774(86)90040-4","volume":"7","author":"P. Tiwari","year":"1986","unstructured":"P. Tiwari An Efficient Parallel Algorithm for Shifting the Root of a Depth First Spanning Tree, Journal of Algorithms, 7, 105\u2013119, (1986).","journal-title":"Journal of Algorithms"},{"key":"6_CR17","doi-asserted-by":"crossref","first-page":"1","DOI":"10.6028\/jres.069B.001","volume":"69B","author":"W.T. Tutte","year":"1965","unstructured":"W.T. Tutte, Lectures on matroids, J. Res. Nat. Bur. Stand. 69B, 1\u201348, (1965).","journal-title":"J. Res. Nat. Bur. Stand."}],"container-title":["Lecture Notes in Computer Science","Graph-Theoretic Concepts in Computer Science"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-50728-0_37","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,1,8]],"date-time":"2020-01-08T23:20:35Z","timestamp":1578525635000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-50728-0_37"}},"subtitle":["Preliminary version"],"short-title":[],"issued":{"date-parts":[[1989]]},"ISBN":["9783540507284","9783540460763"],"references-count":17,"URL":"https:\/\/doi.org\/10.1007\/3-540-50728-0_37","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[1989]]},"assertion":[{"value":"31 May 2005","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}}]}}