The complexity of searching implicit graphs
DOI10.1016/0004-3702(96)00014-8zbMATH Open1506.68117OpenAlexW2079114230MaRDI QIDQ2676567FDOQ2676567
Authors: José L. Balcázar 
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
Recommendations
- The complexity of searching succinctly represented graphs
- New approaches for understanding the asymptotic complexity of \(A^*\) tree searching.
- Space complexity of combinatorial search
- A result on the computational complexity of heuristic estimates for the \(A^*\) algorithm
- Algorithms for searching explicit AND/OR graphs and their applications to problem reduction search
Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)
Cites Work
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- Relationships between nondeterministic and deterministic tape complexities
- Title not available (Why is that?)
- Alternation
- How easy is local search?
- On the complexity of the parity argument and other inefficient proofs of existence
- Provably Difficult Combinatorial Games
- Complete problems for deterministic polynomial time
- Title not available (Why is that?)
- The complexity of combinatorial problems with succinct input representation
- The correlation between the complexities of the nonhierarchical and hierarchical versions of graph problems
- Succinct representations of graphs
- Title not available (Why is that?)
- A note on succinct representations of graphs
- New problems complete for nondeterministic log space
- Space-bounded reducibility among combinatorial problems
- Constant Depth Reducibility
- The Complexity of the Lin–Kernighan Heuristic for the Traveling Salesman Problem
- Title not available (Why is that?)
- A new variant of the \(A^*\)-algorithm which closes a node at most once.
- On Some Deterministic Space Complexity Problems
Cited In (10)
- The complexity of searching a graph
- An efficient algorithm for searching implicit AND/OR graphs with cycles
- Title not available (Why is that?)
- A finite set of functions with an EXPTIME-complete composition problem
- Complexity of searching an immobile hider in a graph
- Representing graphs implicitly using almost optimal space
- Implicit Component-Graph: A Discussion
- A framework for analysing state-abstraction methods
- Heuristic Search for the Analysis of Graph Transition Systems
- Implicit graphs
Uses Software
This page was built for publication: The complexity of searching implicit graphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2676567)
