作者
Amr Elmasry, Torben Hagerup, Frank Kammer
发表日期
2015/2
期刊
32nd International Symposium on Theoretical Aspects of Computer Science (STACS 2015)}
卷号
30
页码范围
288-301
出版商
Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik}
简介
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.
学术搜索中的文章