The complexity of searching implicit graphs

DOI10.1016/0004-3702(96)00014-8MaRDI QIDQ2676567zbMATH OpenOpenAlexFDO

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

Mathematics Subject Classification ID

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)

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

Cites work

• scientific article; zbMATH DE number 4213461 (Why is no real title available?)
• scientific article; zbMATH DE number 3950233 (Why is no real title available?)
• scientific article; zbMATH DE number 192916 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 610968 (Why is no real title available?)
• scientific article; zbMATH DE number 1142309 (Why is no real title available?)
• scientific article; zbMATH DE number 3793772 (Why is no real title available?)
• A new variant of the \(A^*\)-algorithm which closes a node at most once.
• A note on succinct representations of graphs
• Alternation
• Complete problems for deterministic polynomial time
• Constant Depth Reducibility
• How easy is local search?
• New problems complete for nondeterministic log space
• On Some Deterministic Space Complexity Problems
• On the complexity of the parity argument and other inefficient proofs of existence
• Provably Difficult Combinatorial Games
• Relationships between nondeterministic and deterministic tape complexities
• Space-bounded reducibility among combinatorial problems
• Succinct representations of graphs
• The Complexity of the Lin–Kernighan Heuristic for the Traveling Salesman Problem
• The complexity of combinatorial problems with succinct input representation
• The correlation between the complexities of the nonhierarchical and hierarchical versions of graph problems

Cited in

(11)

• Representing graphs implicitly using almost optimal space
• A finite set of functions with an EXPTIME-complete composition problem
• A framework for analysing state-abstraction methods
• Implicit graphs
• The complexity of searching a graph
• Implicit Component-Graph: A Discussion
• scientific article; zbMATH DE number 6851856 (Why is no real title available?)
• An efficient algorithm for searching implicit AND/OR graphs with cycles
• The complexity of searching succinctly represented graphs
• Heuristic Search for the Analysis of Graph Transition Systems
• Complexity of searching an immobile hider in a graph

Describes a project that uses

Uses Software

• LEDA
• Datalog

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)