{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T03:42:06Z","timestamp":1740109326369,"version":"3.37.3"},"reference-count":21,"publisher":"Springer Science and Business Media LLC","issue":"7","license":[{"start":{"date-parts":[[2022,2,26]],"date-time":"2022-02-26T00:00:00Z","timestamp":1645833600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2022,2,26]],"date-time":"2022-02-26T00:00:00Z","timestamp":1645833600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"}],"funder":[{"DOI":"10.13039\/100005156","name":"Alexander von Humboldt-Stiftung","doi-asserted-by":"publisher","award":["Fellowship for experienced researchers"],"award-info":[{"award-number":["Fellowship for experienced researchers"]}],"id":[{"id":"10.13039\/100005156","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2022,7]]},"DOI":"10.1007\/s00453-022-00947-7","type":"journal-article","created":{"date-parts":[[2022,2,26]],"date-time":"2022-02-26T06:02:47Z","timestamp":1645855367000},"page":"2028-2049","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["Fault Tolerant Depth First Search in Undirected Graphs: Simple Yet Efficient"],"prefix":"10.1007","volume":"84","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-8657-7182","authenticated-orcid":false,"given":"Surender","family":"Baswana","sequence":"first","affiliation":[]},{"given":"Shiv","family":"Gupta","sequence":"additional","affiliation":[]},{"given":"Ayush","family":"Tulsyan","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2022,2,26]]},"reference":[{"issue":"2","key":"947_CR1","doi-asserted-by":"publisher","first-page":"397","DOI":"10.1137\/0219025","volume":"19","author":"A Aggarwal","year":"1990","unstructured":"Aggarwal, A., Anderson, R.J., Kao, M.: Parallel depth-first search in general directed graphs. SIAM J. Comput. 19(2), 397\u2013409 (1990). https:\/\/doi.org\/10.1137\/0219025","journal-title":"SIAM J. Comput."},{"key":"947_CR2","doi-asserted-by":"crossref","unstructured":"Baswana, S., Chaudhury, S.R., Choudhary, K., Khan, S.: Dynamic DFS in undirected graphs: Breaking the O(m) barrier. SIAM J. Comput. 48(4), 1335\u20131363 (2019). (A preliminary version appeared in Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, SODA, pp. 730\u2013739, 2016). https:\/\/doi.org\/10.1137\/17M114306X","DOI":"10.1137\/17M114306X"},{"key":"947_CR3","doi-asserted-by":"crossref","unstructured":"Baswana, S., Choudhary, K.: On dynamic DFS tree in directed graphs. In: MFCS, Proceedings, Part II, pp. 102\u2013114 (2015). https:\/\/doi.org\/10.1007\/978-3-662-48054-0_9","DOI":"10.1007\/978-3-662-48054-0_9"},{"key":"947_CR4","doi-asserted-by":"crossref","unstructured":"Baswana, S., Goel, A., Khan, S.: Incremental DFS algorithms: a theoretical and experimental study. In: Czumaj, A. (ed.) Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2018, New Orleans, LA, USA, January 7\u201310, 2018, pp. 53\u201372. SIAM (2018). https:\/\/doi.org\/10.1137\/1.9781611975031.4","DOI":"10.1137\/1.9781611975031.4"},{"key":"947_CR5","unstructured":"Baswana, S., Gupta, S.K., Tulsyan, A.: Fault tolerant and fully dynamic DFS in undirected graphs: simple yet efficient. In: Rossmanith, P., Heggernes, P., Katoen, J.P. (eds.) 44th International Symposium on Mathematical Foundations of Computer Science, MFCS 2019, August 26\u201330, 2019, Aachen, Germany, LIPIcs, vol. 138, pp. 65:1\u201365:16. Schloss Dagstuhl\u2014Leibniz Center for Computer Science (2019). https:\/\/doi.org\/10.4230\/LIPIcs.MFCS.2019.65"},{"issue":"2","key":"947_CR6","doi-asserted-by":"publisher","first-page":"466","DOI":"10.1007\/s00453-016-0204-1","volume":"79","author":"S Baswana","year":"2017","unstructured":"Baswana, S., Khan, S.: Incremental algorithm for maintaining a DFS tree for undirected graphs. Algorithmica 79(2), 466\u2013483 (2017). https:\/\/doi.org\/10.1007\/s00453-016-0204-1","journal-title":"Algorithmica"},{"key":"947_CR7","doi-asserted-by":"crossref","unstructured":"Bernstein, A., Karger, D.R.: A nearly optimal oracle for avoiding failed vertices and edges. In: Proceedings of the 41st Annual ACM Symposium on Theory of Computing, STOC 2009, Bethesda, MD, USA, May 31\u2013June 2, 2009, pp. 101\u2013110 (2009). https:\/\/doi.org\/10.1145\/1536414.1536431","DOI":"10.1145\/1536414.1536431"},{"key":"947_CR8","doi-asserted-by":"crossref","unstructured":"Chan, T.M.: Dynamic subgraph connectivity with geometric applications. In: Proceedings on 34th Annual ACM Symposium on Theory of Computing, May 19\u201321, 2002, Montr\u00e9al, Qu\u00e9bec, Canada, pp. 7\u201313 (2002). https:\/\/doi.org\/10.1145\/509907.509911","DOI":"10.1145\/509907.509911"},{"issue":"2","key":"947_CR9","doi-asserted-by":"publisher","first-page":"133","DOI":"10.1007\/BF01840440","volume":"1","author":"B Chazelle","year":"1986","unstructured":"Chazelle, B., Guibas, L.J.: Fractional cascading: I. A data structuring technique. Algorithmica 1(2), 133\u2013162 (1986). https:\/\/doi.org\/10.1007\/BF01840440","journal-title":"Algorithmica"},{"issue":"7","key":"947_CR10","doi-asserted-by":"publisher","first-page":"3403","DOI":"10.1137\/090758039","volume":"39","author":"S Chechik","year":"2010","unstructured":"Chechik, S., Langberg, M., Peleg, D., Roditty, L.: Fault tolerant spanners for general graphs. SIAM J. Comput. 39(7), 3403\u20133423 (2010). https:\/\/doi.org\/10.1137\/090758039","journal-title":"SIAM J. Comput."},{"key":"947_CR11","unstructured":"Chen, L., Duan, R., Wang, R., Zhang, H.: Improved algorithms for maintaining DFS tree in undirected graphs. CoRR arXiv:1607.04913v2 (2016)"},{"key":"947_CR12","unstructured":"Chen, L., Duan, R., Wang, R., Zhang, H., Zhang, T.: An improved algorithm for incremental DFS tree in undirected graphs. In: SWAT, pp. 16:1\u201316:12 (2018). https:\/\/doi.org\/10.4230\/LIPIcs.SWAT.2018.16"},{"issue":"5","key":"947_CR13","doi-asserted-by":"publisher","first-page":"1299","DOI":"10.1137\/S0097539705429847","volume":"37","author":"C Demetrescu","year":"2008","unstructured":"Demetrescu, C., Thorup, M., Chowdhury, R.A., Ramachandran, V.: Oracles for distances avoiding a failed node or link. SIAM J. Comput. 37(5), 1299\u20131318 (2008). https:\/\/doi.org\/10.1137\/S0097539705429847","journal-title":"SIAM J. Comput."},{"key":"947_CR14","doi-asserted-by":"crossref","unstructured":"Duan, R., Zhang, L.: Faster worst-case update time for dynamic subgraph connectivity. CoRR arXiv:1611.09072 (2016)","DOI":"10.1007\/978-3-319-62127-2_29"},{"issue":"2","key":"947_CR15","doi-asserted-by":"publisher","first-page":"113","DOI":"10.1016\/S0020-0190(96)00202-5","volume":"61","author":"PG Franciosa","year":"1997","unstructured":"Franciosa, P.G., Gambosi, G., Nanni, U.: The incremental maintenance of a depth-first-search tree in directed acyclic graphs. Inf. Process. Lett. 61(2), 113\u2013120 (1997). https:\/\/doi.org\/10.1016\/S0020-0190(96)00202-5","journal-title":"Inf. Process. Lett."},{"issue":"1","key":"947_CR16","doi-asserted-by":"publisher","first-page":"76","DOI":"10.1007\/s004530010032","volume":"28","author":"D Frigioni","year":"2000","unstructured":"Frigioni, D., Italiano, G.F.: Dynamically switching vertices in planar graphs. Algorithmica 28(1), 76\u2013103 (2000). https:\/\/doi.org\/10.1007\/s004530010032","journal-title":"Algorithmica"},{"key":"947_CR17","unstructured":"Grossi, R., Gupta, A., Vitter, J.S.: High-order entropy-compressed text indexes. In: Symposium on Discrete Algorithms, SODA, pp. 841\u2013850 (2003). https:\/\/dl.acm.org\/citation.cfm?id=644108.644250"},{"issue":"3","key":"947_CR18","doi-asserted-by":"publisher","first-page":"52","DOI":"10.3390\/a12030052","volume":"12","author":"K Nakamura","year":"2019","unstructured":"Nakamura, K., Sadakane, K.: Space-efficient fully dynamic DFS in undirected graphs. Algorithms 12(3), 52 (2019). https:\/\/doi.org\/10.3390\/a12030052","journal-title":"Algorithms"},{"issue":"3","key":"947_CR19","doi-asserted-by":"publisher","first-page":"362","DOI":"10.1016\/0022-0000(83)90006-5","volume":"26","author":"DD Sleator","year":"1983","unstructured":"Sleator, D.D., Tarjan, R.E.: A data structure for dynamic trees. J. Comput. Syst. Sci. 26(3), 362\u2013391 (1983). https:\/\/doi.org\/10.1016\/0022-0000(83)90006-5","journal-title":"J. Comput. Syst. Sci."},{"issue":"3","key":"947_CR20","doi-asserted-by":"publisher","first-page":"814","DOI":"10.1137\/0215058","volume":"15","author":"JR Smith","year":"1986","unstructured":"Smith, J.R.: Parallel algorithms for depth-first searches I. planar graphs. SIAM J. Comput. 15(3), 814\u2013830 (1986)","journal-title":"SIAM J. Comput."},{"issue":"2","key":"947_CR21","doi-asserted-by":"publisher","first-page":"146","DOI":"10.1137\/0201010","volume":"1","author":"RE Tarjan","year":"1972","unstructured":"Tarjan, R.E.: Depth-first search and linear graph algorithms. SIAM J. Comput. 1(2), 146\u2013160 (1972). https:\/\/doi.org\/10.1137\/0201010","journal-title":"SIAM J. Comput."}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-022-00947-7.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00453-022-00947-7\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-022-00947-7.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,6,23]],"date-time":"2022-06-23T11:05:04Z","timestamp":1655982304000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00453-022-00947-7"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,2,26]]},"references-count":21,"journal-issue":{"issue":"7","published-print":{"date-parts":[[2022,7]]}},"alternative-id":["947"],"URL":"https:\/\/doi.org\/10.1007\/s00453-022-00947-7","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"type":"print","value":"0178-4617"},{"type":"electronic","value":"1432-0541"}],"subject":[],"published":{"date-parts":[[2022,2,26]]},"assertion":[{"value":"26 August 2020","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"31 January 2022","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"26 February 2022","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}