Problems complete for deterministic logarithmic space. (English) Zbl 0644.68058

Cook, Stephen A.; McKenzie, Pierre

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

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