Cook, Stephen A.; McKenzie, Pierre Problems complete for deterministic logarithmic space. (English) Zbl 0644.68058 J. Algorithms 8, 385-394 (1987). A number of graph problems are shown to be complete for deterministic logarithmic space under logarithmic depth \((NC^ 1)\) reductions, including breadth-first and depth-first labelling of a graph. The basic tool used is the determination of some complete problems on permutations, including the problem: given a pointwise representation of a permutation, determine whether it acts as a single cycle. It is also established that connectivity of undirected graphs is \(NC^ 1\)-hard for deterministic log space. Reviewer: C.J.Colburn Cited in 3 ReviewsCited in 40 Documents MSC: 68Q25 Analysis of algorithms and problem complexity 68R10 Graph theory (including graph drawing) in computer science Keywords:breadth-first search; depth-first search; deterministic logarithmic space; labelling; connectivity of undirected graphs; log space PDF BibTeX XML Cite \textit{S. A. Cook} and \textit{P. McKenzie}, J. Algorithms 8, 385--394 (1987; Zbl 0644.68058) Full Text: DOI OpenURL