Biconnectivity, st-numbering and other applications of DFS using O(n) bits.

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 1 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 lg c 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. [ABSTRACT FROM AUTHOR]