  Read-only memory model is a classical model of computation to study
time-space tradeoffs of algorithms. One of the classical results on the ROM
model is that any sorting algorithm that uses O(s) words of extra space
requires $\Omega (n^2/s)$ comparisons for $ \lg n \leq s \leq n/\lg n$ and the
bound has also been recently matched by an algorithm. However, if we relax the
model (from ROM), we do have sorting algorithms (say Heapsort) that can sort
using $O(n \lg n)$ comparisons using $O(\lg n)$ bits of extra space, even
keeping a permutation of the given input sequence at any point of time during
the algorithm.
  We address similar questions for graph algorithms. We show that a simple
natural relaxation of ROM model allows us to implement fundamental graph search
methods like BFS and DFS more space efficiently than in ROM. By simply allowing
elements in the adjacency list of a vertex to be permuted, we show that, on an
undirected or directed connected graph $G$ having $n$ vertices and $m$ edges,
the vertices of $G$ can be output in a DFS or BFS order using $O(\lg n)$ bits
of extra space and $O(n^3 \lg n)$ time. Thus we obtain similar bounds for
reachability and shortest path distance (both for undirected and directed
graphs). With a little more (but still polynomial) time, we can also output
vertices in the lex-DFS order. As reachability in directed graphs and shortest
path distance are NL-complete, and lex-DFS is P-complete, our results show that
our model is more powerful than ROM if L $\neq$ P. En route, we also introduce
and develop algorithms for another relaxation of ROM where the adjacency lists
of the vertices are circular lists and we can modify only the heads of the
lists. 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.
