Frameworks for designing in-place graph algorithms (Q2237887)

This paper studies the BFS, breadth-first search, and the DFS, depth-first search, algorithms for graphs in rotate and sharp models. The input graph \(G=(V,E)\) with \(n\) vertices and \(m\) edges is represented as an array of length \(n\) representing vertices with pointers to the adjacency list of vertex \(i\), and each adjacency list is a singly linked list. The graph representation cannot be modified in ROM models, however, in rotate and implicit models, this limitation is relaxed for either the vertex array or the adjacency lists, not both. In the implicit model, the vertex array is read-only, however, two adjacent nodes in a linked list can be swapped in constant time (no change in the graph structure happens). In the rotate model, the adjacency linked lists are read-only, however, one can change the entries of the vertex array in just the following way: instead of pointing to the first node of the corresponding adjacency linked list, it can point to any other node in the adjacency linked list. The authors show that the BFS and the DFS algorithms can be accomplished in both of these models in polynomial time. The authors also study the problem of the minimum spanning tree in these models. Their algorithm is a logspace one, but with almost a large time complexity.