Frameworks for designing in-place graph algorithms
Peer reviewed, Journal article
Published version
Permanent lenke
https://hdl.handle.net/11250/3058186Utgivelsesdato
2022Metadata
Vis full innførselSamlinger
Sammendrag
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.