查看文章

We reconsider basic algorithmic graph problems in a setting where an n-vertex input graph is read-only and the computation must take place in a working memory of O (n) bits or little more than that. For computing connected components and performing breadth-first search, we match the running times of standard algorithms that have no memory restrictions, for depth-first search and related problems we come within a factor of Θ (log log n), and for computing minimum spanning forests and single-source shortest-paths trees we come close for sparse input graphs.