The complexity of searching implicit graphs
DOI10.1016/0004-3702(96)00014-8zbMath1506.68117OpenAlexW2079114230MaRDI QIDQ2676567
Publication date: 27 September 2022
Published in: Artificial Intelligence (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/0004-3702(96)00014-8
Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)
Related Items (3)
Uses Software
Cites Work
- The complexity of combinatorial problems with succinct input representation
- How easy is local search?
- The correlation between the complexities of the nonhierarchical and hierarchical versions of graph problems
- Space-bounded reducibility among combinatorial problems
- Complete problems for deterministic polynomial time
- On the complexity of the parity argument and other inefficient proofs of existence
- A new variant of the \(A^*\)-algorithm which closes a node at most once.
- Relationships between nondeterministic and deterministic tape complexities
- Constant Depth Reducibility
- Succinct representations of graphs
- Provably Difficult Combinatorial Games
- Alternation
- On Some Deterministic Space Complexity Problems
- The Complexity of the Lin–Kernighan Heuristic for the Traveling Salesman Problem
- New problems complete for nondeterministic log space
- A note on succinct representations of graphs
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
This page was built for publication: The complexity of searching implicit graphs
