2016/06/28 by Sankardeep Chakraborty, Chakraborty, Sankardeep, Venkatesh Raman +3 · 1 citation
Computer Science · #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #cs.DS
paper · pdf · doi:10.48550/arxiv.1606.08645
18 pages, 4 figures, Preliminary version of this article appeared in the proceedings of 27th ISAAC 2016, Journal version is accepted to JCSS and will soon appear
arxiv created 2017/07/27 · arxiv updated 2017/07/28
We consider space efficient implementations of some classical applications of DFS including the problem of testing biconnectivity and 2-edge connectivity, finding cut vertices and cut edges, computing chain decomposition and st-numbering of a given undirected graph G on n vertices and m edges. Classical algorithms for them typically use DFS and some Ω(\lg n) bits\footnoteWe use \lg to denote logarithm to the base 2. of information at each vertex. Building on a recent O(n)-bits implementation of DFS due to Elmasry et al. (STACS 2015) we provide O(n)-bit implementations for all these applications of DFS. Our algorithms take O(m \lgc n \lg\lg n) time for some small constant c (where c ≤ 2). Central to our implementation is a succinct representation of the DFS tree and a space efficient partitioning of the DFS tree into connected subtrees, which maybe of independent interest for designing other space efficient graph algorithms.