Alladi Ramakrishnan Hall

Space Efficient Graph Algorithms (Thesis Defence)

Sankardeep Chakraborty

This thesis focusses on an emerging area of making algorithms for some fundamental graph problems, space efficient while maintaining efficiency in time as well.

We provide such algorithms for various graph search methods (depth first search, breadth first search, maximum cardinality search), connectivity problems (biconnectivity, 2-edge connectivity and strong connectivity), testing chordality of a graph etc in the red-only memory model using $O(n)$ bits. Most of these results require techniques from succinct data structure world along with suitable modifications of the existing graph algorithms.

We also introduce two new frameworks for designing efficient {\it in-place} graph algorithms and obtain such algorithms for multiple basic algorithmic graph problems as well.
For example, we provide algorithms for DFS and BFS using O(log n) bits of extra space albeit with super-linear running time. In contrast, there is no algorithm for DFS that takes sublinear space in the read-only memory model.