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


68Q25 Analysis of algorithms and problem complexity
68R10 Graph theory (including graph drawing) in computer science
Full Text: DOI