Problems complete for deterministic logarithmic space
From MaRDI portal
Publication:3787477
DOI10.1016/0196-6774(87)90018-6zbMath0644.68058OpenAlexW1990870868WikidataQ59567327 ScholiaQ59567327MaRDI QIDQ3787477
Pierre McKenzie, Stephen A. Cook
Publication date: 1987
Published in: Journal of Algorithms (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/0196-6774(87)90018-6
labellingdepth-first searchbreadth-first searchdeterministic logarithmic spacelog spaceconnectivity of undirected graphs
Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10)
Related Items (44)
Equivalence classes and conditional hardness in massively parallel computations ⋮ Computation by interaction for space-bounded functional programming ⋮ Complexity models for incremental computation ⋮ The arithmetic complexity of tensor contraction ⋮ The complexity of planarity testing ⋮ Monomials, multilinearity and identity testing in simple read-restricted circuits ⋮ On the parallel complexity of linear groups ⋮ A note on logspace optimization ⋮ Counting quantifiers, successor relations, and logarithmic space ⋮ The complexity of intersecting finite automata having few final states ⋮ A new complete language for DSPACE(log n) ⋮ Finding regular subgraphs in both arbitrary and planar graphs ⋮ Isomorphism testing of read-once functions and polynomials ⋮ On the complexity of inverse semigroup conjugacy ⋮ McNaughton families of languages. ⋮ Completeness results for graph isomorphism. ⋮ The word problem for finitary automaton groups ⋮ Unnamed Item ⋮ A logspace solution to the word and conjugacy problem of generalized Baumslag-Solitar groups ⋮ Pure Pointer Programs with Iteration ⋮ Distributed XML design ⋮ How to meet in anonymous network ⋮ Interleaved Group Products ⋮ Oracle branching programs and Logspace versus \(P^*\) ⋮ The expressiveness of a family of finite set languages ⋮ The complexity of circuit value and network stability ⋮ Extensions to Barrington's M-program model ⋮ Low complexity algorithms in knot theory ⋮ On the complexity of matrix rank and rigidity ⋮ On measures of space over real and complex numbers ⋮ On the complexity of some problems on groups input as multiplication tables ⋮ Approximation in (Poly-) logarithmic space ⋮ Planar and grid graph reachability problems ⋮ On the complexity of topological sorting ⋮ Investigations Concerning the Structure of Complete Sets ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Parameterized complexity of finding regular induced subgraphs ⋮ Deterministic and randomized bounded truth-table reductions of P, NL, and L to sparse sets ⋮ Reversible space equals deterministic space ⋮ PARALLEL VERTEX COLOURING OF INTERVAL GRAPHS ⋮ On the computational complexity of reachability in 2D binary images and some basic problems of 2D digital topology ⋮ Two-coloring linked lists is NC\(^ 1\)-complete for logarithmic space ⋮ Dynamic complexity of expansion
This page was built for publication: Problems complete for deterministic logarithmic space
