{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,19]],"date-time":"2026-05-19T07:19:20Z","timestamp":1779175160534,"version":"3.51.4"},"reference-count":24,"publisher":"Association for Computing Machinery (ACM)","issue":"2","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Proc. VLDB Endow."],"published-print":{"date-parts":[[2019,10]]},"abstract":"<jats:p>Depth-first search (DFS) is a fundamental and important algorithm in graph analysis. It is the basis of many graph algorithms such as computing strongly connected components, testing planarity, and detecting biconnected components. The result of a DFS is normally shown as a DFS-Tree. Given the frequent updates in many real-world graphs (e.g., social networks and communication networks), we study the problem of DFS-Tree maintenance in dynamic directed graphs. In the literature, most works focus on the DFS-Tree maintenance problem in undirected graphs and directed acyclic graphs. However, their methods cannot easily be applied in the case of general directed graphs. Motivated by this, we propose a framework and corresponding algorithms for both edge insertion and deletion in general directed graphs. We further give several optimizations to speed up the algorithms. We conduct extensive experiments on 12 real-world datasets to show the efficiency of our proposed algorithms.<\/jats:p>","DOI":"10.14778\/3364324.3364329","type":"journal-article","created":{"date-parts":[[2020,9,11]],"date-time":"2020-09-11T03:16:00Z","timestamp":1599794160000},"page":"142-154","source":"Crossref","is-referenced-by-count":17,"title":["Fully dynamic depth-first search in directed graphs"],"prefix":"10.14778","volume":"13","author":[{"given":"Bohua","family":"Yang","sequence":"first","affiliation":[{"name":"University of Technology Sydney, Australia"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Dong","family":"Wen","sequence":"additional","affiliation":[{"name":"University of Technology Sydney, Australia"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Lu","family":"Qin","sequence":"additional","affiliation":[{"name":"University of Technology Sydney, Australia"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Ying","family":"Zhang","sequence":"additional","affiliation":[{"name":"University of Technology Sydney, Australia"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Xubo","family":"Wang","sequence":"additional","affiliation":[{"name":"University of Technology Sydney, Australia"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Xuemin","family":"Lin","sequence":"additional","affiliation":[{"name":"The University of New South Wales, Australia"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2019,10]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611974331.ch52"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-48054-0_9"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611975031.4"},{"key":"e_1_2_1_4_1","volume-title":"Fault tolerant and fully dynamic DFS in undirected graphs: simple yet efficient. arXiv preprint arXiv:1810.01726","author":"Baswana S.","year":"2018"},{"key":"e_1_2_1_5_1","volume-title":"Improved algorithms for maintaining DFS tree in undirected graphs. CoRR, abs\/1607.04913","author":"Chen L.","year":"2016"},{"key":"e_1_2_1_6_1","volume-title":"16th Scandinavian Symposium and Workshops on Algorithm Theory","author":"Chen L.","year":"2018"},{"key":"e_1_2_1_7_1","volume-title":"Introduction to algorithms","author":"Cormen T. H.","year":"2009"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1142\/S0129054106004248"},{"key":"e_1_2_1_9_1","volume-title":"A discipline of programming","author":"Dijkstra E. W.","year":"1976"},{"key":"e_1_2_1_10_1","volume-title":"The incremental maintenance of a depth-first-search tree in directed acyclic graphs. Information processing letters, 61(2):113--120","author":"Franciosa P. G.","year":"1997"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/362248.362272"},{"key":"e_1_2_1_12_1","volume-title":"Efficient planarity testing. Journal of the ACM (JACM), 21(4):549--568","author":"Hopcroft J.","year":"1974"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(94)90159-7"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-53925-6_23"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(85)90024-9"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(87)90095-0"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1016\/0898-1221(81)90008-0"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/564870.564917"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2016.2631160"},{"key":"e_1_2_1_20_1","series-title":"SIAM journal on computing, 1(2):146--160","volume-title":"Depth-first search and linear graph algorithms","author":"Tarjan R.","year":"1972"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(74)90003-9"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF00268499"},{"key":"e_1_2_1_23_1","unstructured":"A. Tucker. Chapter 2: covering circuits and graph colorings. Applied Combinatorics 49 2006.  A. Tucker. Chapter 2: covering circuits and graph colorings. Applied Combinatorics 49 2006."},{"issue":"1","key":"e_1_2_1_24_1","first-page":"276","article-title":"Grail: scalable reachability index for large graphs","volume":"3","author":"Yildirim H.","year":"2010","journal-title":"PVLDB"}],"container-title":["Proceedings of the VLDB Endowment"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.14778\/3364324.3364329","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,12,28]],"date-time":"2022-12-28T10:59:35Z","timestamp":1672225175000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.14778\/3364324.3364329"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,10]]},"references-count":24,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2019,10]]}},"alternative-id":["10.14778\/3364324.3364329"],"URL":"https:\/\/doi.org\/10.14778\/3364324.3364329","relation":{},"ISSN":["2150-8097"],"issn-type":[{"value":"2150-8097","type":"print"}],"subject":[],"published":{"date-parts":[[2019,10]]}}}