DROPS (Schloss Dagstuhl – Leibniz Center for Informatics) · 2015 · 23 citations · 0 references
ComputingComputer ScienceAlgorithmsData StructuresTheory Of ComputationAlgorithm AnalysisComputational ComplexityGraph AlgorithmsGraph TheoryShortest Path AlgorithmsSpace ComplexityAlgorithmic Graph TheoryBreadth-first SearchComputational Complexity Of Graph AlgorithmsDepth-first SearchShortest PathsSingle-source Shortest PathsSpace Complexity Of Graph ProblemsTree Algorithms
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 \Theta(\log\log n), and for computing minimum spanning forests and single-source shortest-paths trees we come close for sparse input graphs.