Abstract
Recent work by Elmasry et al. (STACS 2015) and Asano et al. (ISAAC 2014) reconsidered classical fundamental graph algorithms focusing on improving the space complexity. Elmasry et al. gave, among others, an implementation of depth first search (DFS) of a graph on n vertices and m edges, taking O(m lg lg n) time using O(n) bits of space improving on the time bound of O(m lg n) due to Asano et al. Subsequently Banerjee et al. (COCOON 2016) gave an O(m + n) time implementation using O(m+n) bits, for DFS and its classical applications (including testing for biconnectivity, and finding cut vertices and cut edges). Recently, Kammer et al. (MFCS 2016) gave an algorithm for testing biconnectivity using O(n + min{m, n lg lg n}) bits in linear time.
In this paper, we consider O(n) bits implementations of the classical applications of DFS. These include the problem of finding cut vertices, and biconnected components, chain decomposition and stnumbering. Classical algorithms for them typically use DFS and some Omega(lg n) bits of information at each node. Our O(n)bit implementations for these problems take O(m lg^c n lg lg n) time for some small constant c (c leq 3). 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 space efficient graph algorithms.
BibTeX  Entry
@InProceedings{chakraborty_et_al:LIPIcs:2016:6792,
author = {Sankardeep Chakraborty and Venkatesh Raman and Srinivasa Rao Satti},
title = {{Biconnectivity, Chain Decomposition and stNumbering Using O(n) Bits}},
booktitle = {27th International Symposium on Algorithms and Computation (ISAAC 2016)},
pages = {22:122:13},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959770262},
ISSN = {18688969},
year = {2016},
volume = {64},
editor = {SeokHee Hong},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2016/6792},
URN = {urn:nbn:de:0030drops67927},
doi = {10.4230/LIPIcs.ISAAC.2016.22},
annote = {Keywords: biconnectivity, stnumber, chain decomposition, tree cover, space efficient algorithms, readonly memory}
}
Keywords: 

biconnectivity, stnumber, chain decomposition, tree cover, space efficient algorithms, readonly memory 
Collection: 

27th International Symposium on Algorithms and Computation (ISAAC 2016) 
Issue Date: 

2016 
Date of publication: 

07.12.2016 