The complexity of searching succinctly represented graphs

DOI10.1007/3-540-60084-1_75MaRDI QIDQ4645179zbMATH OpenOpenAlexFDO

Authors José L. Balcázar

Publication date 10 January 2019

Published in Automata, Languages and Programming (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/3-540-60084-1_75

zbMATH Keywords

Boolean circuitcomplexity classgoal vertexpolynomial timetrivial graph

Mathematics Subject Classification ID

Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) 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)

Recommendations

• The complexity of searching implicit graphs
• Space complexity of combinatorial search
• New approaches for understanding the asymptotic complexity of \(A^*\) tree searching.
• A result on the computational complexity of heuristic estimates for the A^* algorithm
• Succinct representations of graphs

Cites work

• 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?
• 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?)
• 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 combinatorial problems with succinct input representation
• The Complexity of the Lin–Kernighan Heuristic for the Traveling Salesman Problem
• The correlation between the complexities of the nonhierarchical and hierarchical versions of graph problems

Cited in

(10)

• Complexity of searching an immobile hider in a graph
• The complexity of searching implicit graphs
• An accelerated search on the graph: PROLOG representation
• Equality Testing of Compressed Strings
• Heuristic Search for the Analysis of Graph Transition Systems
• The complexity of searching a graph
• scientific article; zbMATH DE number 33703 (Why is no real title available?)
• scientific article; zbMATH DE number 219271 (Why is no real title available?)
• A note on succinct representations of graphs
• On the succinct representation of graphs

Describes a project that uses

Uses Software

• Datalog
• LEDA

This page was built for publication: The complexity of searching succinctly represented graphs

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