scientific article; zbMATH DE number 3555903

Cited in

(62)

The three-color and two-color Tantrix\(^{\text{TM}}\) rotation puzzle problems are NP-complete via parsimonious reductions
An introduction to parallelism in combinatorial optimization
On the construction of parallel computers from various basis of Boolean functions
Parallelism and the maximal path problem
The word and generator problems for lattices
How easy is local search?
Parallelism and the feedback vertex set problem
[[:Publication:1118407|The logarithmic alternation hierarchy collapses: \(A\Sigma _ 2^Template:\mathcal L=A\Pi_ 2^Template:\mathcal L\)]]
On computing graph closures
A space efficient algorithm for the monotone planar circuit value problem
Number of quantifiers is better than number of tape cells
The maximum flow problem is log space complete for P
The complexity of short two-person games
Properties that characterize LOGCFL
\(\Delta{} ^ p_ 2\)-complete lexicographically first maximal subgraph problems
Oracle branching programs and Logspace versus \(P^*\)
The correlation between the complexities of the nonhierarchical and hierarchical versions of graph problems
The complexity of circuit value and network stability
Positive versions of polynomial time
Finding the closed partition of a planar graph
A theory of strict P-completeness
On the computational complexity of graph closures
Parallel evaluation of arithmetic circuits
A recognition and parsing algorithm for arbitrary conjunctive grammars.
Tree-width and the monadic quantifier hierarchy.
Balancing bounded treewidth circuits
The complexity of synchronizing Markov decision processes
TANTRIX\(^{\text{TM}}\) rotation puzzles are intractable
Module checking
On the computational complexity of data flow analysis over finite bounded meet semilattices
On the complexity of asynchronous freezing cellular automata
Who witnesses The Witness? Finding witnesses in The Witness is hard and sometimes impossible
On the complexity of the stability problem of binary freezing totalistic cellular automata
Two dynamic programming algorithms for which interpreted pebbling helps
Matchstick puzzles on a grid
Games for active XML revisited
Graph isomorphism, color refinement, and compactness
The complexity of agent design problems: Determinism and history dependence
The monotone circuit value problem with bounded genus is in NC
On the structure of solution-graphs for Boolean formulas
On the parameterized parallel complexity and the vertex cover problem
Isomorphism of regular trees and words
The complexity of intersecting finite automata having few final states
The Three-Color and Two-Color TantrixTM Rotation Puzzle Problems Are NP-Complete Via Parsimonious Reductions
The parallel complexity of approximation algorithms for the maximum acyclic subgraph problem
A theory of strict P-completeness
Model checking and validity in propositional and modal inclusion logics
Ordered vertex removal and subgraph problems
Formal languages over GF(2)
The complexity gap in the static analysis of cache accesses grows if procedure calls are added
Embedding arbitrary Boolean circuits into fungal automata
A simple P-complete problem and its language-theoretic representations
Embedding arbitrary Boolean circuits into fungal automata
Evaluating monotone circuits on surfaces
Computational complexity of the Weisfeiler-Leman dimension
Computational complexity of the Weisfeiler-Leman dimension
Universality frontier for asynchronous cellular automata
The complexity of games with randomised control
The complexity of membership problems for circuits over sets of integers
The binary network flow problem is logspace complete for P
A P-complete graph partition problem
On short paths interdiction problems: Total and node-wise limited interdiction

This page was built for publication:

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4128417)