{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,5,29]],"date-time":"2025-05-29T04:26:25Z","timestamp":1748492785417,"version":"3.37.3"},"reference-count":23,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2016,8,26]],"date-time":"2016-08-26T00:00:00Z","timestamp":1472169600000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2017,10]]},"DOI":"10.1007\/s00453-016-0204-1","type":"journal-article","created":{"date-parts":[[2016,8,26]],"date-time":"2016-08-26T10:27:28Z","timestamp":1472207248000},"page":"466-483","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":3,"title":["Incremental Algorithm for Maintaining a DFS Tree for Undirected Graphs"],"prefix":"10.1007","volume":"79","author":[{"given":"Surender","family":"Baswana","sequence":"first","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0001-9352-0088","authenticated-orcid":false,"given":"Shahbaz","family":"Khan","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2016,8,26]]},"reference":[{"key":"204_CR1","doi-asserted-by":"crossref","unstructured":"Alstrup, S., Holm, J.: Improved algorithms for finding level ancestors in dynamic trees. In: Proceedings of Automata, Languages and Programming, 27th International Colloquium, ICALP 2000, Geneva, Switzerland, 9\u201315 July 2000, pp. 73\u201384 (2000)","DOI":"10.1007\/3-540-45022-X_8"},{"key":"204_CR2","doi-asserted-by":"crossref","unstructured":"Baswana, S., Choudhary, K.: On dynamic DFS tree in directed graphs. In: Proceedings of Part II Mathematical Foundations of Computer Science 2015\u201440th International Symposium, MFCS 2015, Milan, Italy, 24\u201328 Aug 2015, pp. 102\u2013114 (2015)","DOI":"10.1007\/978-3-662-48054-0_9"},{"key":"204_CR3","doi-asserted-by":"crossref","unstructured":"Baswana, S., Khan, S.: Incremental algorithm for maintaining DFS tree for undirected graphs. In: Proceedings of Part I Automata, Languages, and Programming\u201441st International Colloquium, ICALP 2014, Copenhagen, Denmark, 8\u201311 July 2014, , pp. 138\u2013149 (2014)","DOI":"10.1007\/978-3-662-43948-7_12"},{"issue":"4","key":"204_CR4","doi-asserted-by":"crossref","first-page":"35","DOI":"10.1145\/2344422.2344425","volume":"8","author":"S Baswana","year":"2012","unstructured":"Baswana, S., Khurana, S., Sarkar, S.: Fully dynamic randomized algorithms for graph spanners. ACM Trans. Algorithms 8(4), 35 (2012)","journal-title":"ACM Trans. Algorithms"},{"issue":"4","key":"204_CR5","doi-asserted-by":"crossref","first-page":"894","DOI":"10.1137\/S0097539700370539","volume":"34","author":"R Cole","year":"2005","unstructured":"Cole, R., Hariharan, R.: Dynamic lca queries on trees. SIAM J. Comput. 34(4), 894\u2013923 (2005)","journal-title":"SIAM J. Comput."},{"issue":"6","key":"204_CR6","doi-asserted-by":"crossref","first-page":"968","DOI":"10.1145\/1039488.1039492","volume":"51","author":"C Demetrescu","year":"2004","unstructured":"Demetrescu, C., Italiano, G.F.: A new approach to dynamic all pairs shortest paths. J. ACM 51(6), 968\u2013992 (2004)","journal-title":"J. ACM"},{"issue":"5","key":"204_CR7","doi-asserted-by":"crossref","first-page":"669","DOI":"10.1145\/265910.265914","volume":"44","author":"D Eppstein","year":"1997","unstructured":"Eppstein, D., Galil, Z., Italiano, G.F., Nissenzweig, A.: Sparsification\u2014a technique for speeding up dynamic graph algorithms. J. ACM 44(5), 669\u2013696 (1997)","journal-title":"J. ACM"},{"key":"204_CR8","unstructured":"Erd\u0151s, P., R\u00e9nyi, A.: On the evolution of random graphs. In: Publications of the Mathematical Institute of the Hungarian Academy of Sciences, vol. 5, pp. 17\u201361 (1960)"},{"issue":"2","key":"204_CR9","doi-asserted-by":"crossref","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)","journal-title":"Inf. Process. Lett."},{"key":"204_CR10","unstructured":"Gottlieb, L., Roditty, L.: Improved algorithms for fully dynamic geometric spanners and geometric routing. In: Proceedings of the Nineteenth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA, vol. 2008 2008, pp. 591\u2013600 (2008)"},{"issue":"4","key":"204_CR11","doi-asserted-by":"crossref","first-page":"502","DOI":"10.1145\/320211.320215","volume":"46","author":"MR Henzinger","year":"1999","unstructured":"Henzinger, M.R., King, V.: Randomized fully dynamic graph algorithms with polylogarithmic time per operation. J. ACM 46(4), 502\u2013516 (1999)","journal-title":"J. ACM"},{"issue":"4","key":"204_CR12","doi-asserted-by":"crossref","first-page":"723","DOI":"10.1145\/502090.502095","volume":"48","author":"J Holm","year":"2001","unstructured":"Holm, J., de Lichtenberg, K., Thorup, M.: Poly-logarithmic deterministic fully-dynamic algorithms for connectivity, minimum spanning tree, 2-edge, and biconnectivity. J. ACM 48(4), 723\u2013760 (2001)","journal-title":"J. ACM"},{"key":"204_CR13","doi-asserted-by":"crossref","unstructured":"Kapron, B.M., King, V., Mountjoy, B.: Dynamic graph connectivity in polylogarithmic worst case time. In: Proceedings of the Twenty-Fourth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2013, New Orleans, Louisiana, USA, 6\u20138 January 2013, pp. 1131\u20131142 (2013)","DOI":"10.1137\/1.9781611973105.81"},{"issue":"2","key":"204_CR14","doi-asserted-by":"crossref","first-page":"131","DOI":"10.1002\/rsa.20470","volume":"43","author":"M Krivelevich","year":"2013","unstructured":"Krivelevich, M., Sudakov, B.: The phase transition in random graphs: a simple proof. Random Struct. Algorithms 43(2), 131\u2013138 (2013)","journal-title":"Random Struct. Algorithms"},{"issue":"1","key":"204_CR15","doi-asserted-by":"crossref","first-page":"203","DOI":"10.1016\/0304-3975(94)90159-7","volume":"130","author":"PB Miltersen","year":"1994","unstructured":"Miltersen, P.B., Subramanian, S., Vitter, J.S., Tamassia, R.: Complexity models for incremental computation. Theor. Comput. Sci. 130(1), 203\u2013236 (1994)","journal-title":"Theor. Comput. Sci."},{"issue":"5","key":"204_CR16","doi-asserted-by":"crossref","first-page":"229","DOI":"10.1016\/0020-0190(85)90024-9","volume":"20","author":"JH Reif","year":"1985","unstructured":"Reif, J.H.: Depth-first search is inherently sequential. Inf. Process. Lett. 20(5), 229\u2013234 (1985)","journal-title":"Inf. Process. Lett."},{"issue":"1","key":"204_CR17","doi-asserted-by":"crossref","first-page":"65","DOI":"10.1016\/0020-0190(87)90095-0","volume":"25","author":"JH Reif","year":"1987","unstructured":"Reif, J.H.: A topological approach to dynamic graph connectivity. Inf. Process. Lett. 25(1), 65\u201370 (1987)","journal-title":"Inf. Process. Lett."},{"issue":"3\u20134","key":"204_CR18","doi-asserted-by":"crossref","first-page":"1073","DOI":"10.1007\/s00453-011-9504-7","volume":"62","author":"L Roditty","year":"2012","unstructured":"Roditty, L.: Fully dynamic geometric spanners. Algorithmica 62(3\u20134), 1073\u20131087 (2012)","journal-title":"Algorithmica"},{"issue":"5","key":"204_CR19","doi-asserted-by":"crossref","first-page":"1455","DOI":"10.1137\/060650271","volume":"37","author":"L Roditty","year":"2008","unstructured":"Roditty, L., Zwick, U.: Improved dynamic reachability algorithms for directed graphs. SIAM J. Comput. 37(5), 1455\u20131471 (2008)","journal-title":"SIAM J. Comput."},{"issue":"3","key":"204_CR20","doi-asserted-by":"crossref","first-page":"670","DOI":"10.1137\/090776573","volume":"41","author":"L Roditty","year":"2012","unstructured":"Roditty, L., Zwick, U.: Dynamic approximate all-pairs shortest paths in undirected graphs. SIAM J. Comput. 41(3), 670\u2013683 (2012)","journal-title":"SIAM J. Comput."},{"key":"204_CR21","doi-asserted-by":"crossref","unstructured":"Sankowski, P.: Dynamic transitive closure via dynamic matrix inverse (extended abstract). In: Proceedings of 45th Symposium on Foundations of Computer Science (FOCS 2004), pp. 509\u2013517 (2004)","DOI":"10.1109\/FOCS.2004.25"},{"issue":"2","key":"204_CR22","doi-asserted-by":"crossref","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)","journal-title":"SIAM J. Comput."},{"issue":"1","key":"204_CR23","doi-asserted-by":"crossref","first-page":"91","DOI":"10.1007\/s00493-007-0045-2","volume":"27","author":"M Thorup","year":"2007","unstructured":"Thorup, M.: Fully-dynamic min-cut. Combinatorica 27(1), 91\u2013127 (2007)","journal-title":"Combinatorica"}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00453-016-0204-1\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-016-0204-1.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-016-0204-1","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-016-0204-1.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2017,7,31]],"date-time":"2017-07-31T14:37:12Z","timestamp":1501511832000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00453-016-0204-1"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016,8,26]]},"references-count":23,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2017,10]]}},"alternative-id":["204"],"URL":"https:\/\/doi.org\/10.1007\/s00453-016-0204-1","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"type":"print","value":"0178-4617"},{"type":"electronic","value":"1432-0541"}],"subject":[],"published":{"date-parts":[[2016,8,26]]}}}