BARC talk by Shahbaz Khan – University of Copenhagen
Summary
Wednesday, 25 March 2020, Shahbaz Khan, Postdoc at the University of Helsinki, will give a talk on "Incremental DFS algorithms: a theoretical and experimental study". Abstract: The depth first search (DFS) tree is a fundamental data structure used for solving various graph problems. However, even after 20 years of this result, there does not exist any non-trivial incremental algorithm for maintaining a DFS tree in directed graphs with o(m2) worst case bound. For insertion of a uniformly random sequence of edges, each of ADFS1, ADFS2 and FDFS perform equally well and are found to take Θ(n2) time experimentally. We complement this experimental result with a probabilistic analysis of these algorithms establishing Õ(n2) bound on their time complexity.