Frameworks for designing in-place graph algorithms

Abstract

Read-only memory (ROM) model is a classical model of computation to study time-space tradeoffs of algorithms. More recently, several graph algorithms have been studied under ROM model. In this paper, we study graph algorithms under two different relaxations of ROM model, referred to as the implicit and rotate models, and show that these simple relaxations allow us to implement fundamental graph search methods like BFS and DFS more space efficiently than in ROM model. All our algorithms are simple but quite subtle, and we believe that these models are practical enough to spur interest for other graph problems in these models.