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

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
Full Text: