Back to Search
Start Over
Biconnectivity, st-numbering and other applications of DFS using O(n) bits.
- Source :
-
Journal of Computer & System Sciences . Dec2017, Vol. 90, p63-79. 17p. - Publication Year :
- 2017
-
Abstract
- 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]
- Subjects :
- *DISTRIBUTED computing
*BIT rate
*GRAPH connectivity
*COMPUTER algorithms
*SUBGRAPHS
Subjects
Details
- Language :
- English
- ISSN :
- 00220000
- Volume :
- 90
- Database :
- Academic Search Index
- Journal :
- Journal of Computer & System Sciences
- Publication Type :
- Academic Journal
- Accession number :
- 125179293
- Full Text :
- https://doi.org/10.1016/j.jcss.2017.06.006